1534. Count Good Triplets

EasyArrayEnumeration
Leetcode Link

Problem Description

In this problem, we are provided with an array of integers arr and three separate integers a, b, and c. Our goal is to determine how many triplets (arr[i], arr[j], arr[k]) meet certain criteria, where i, j, and k are distinct indices into the array with i < j < k.

A triplet is considered "good" if it satisfies the following conditions:

  • The absolute difference between arr[i] and arr[j] is less than or equal to a.
  • The absolute difference between arr[j] and arr[k] is less than or equal to b.
  • The absolute difference between arr[i] and arr[k] is less than or equal to c.

The problem asks us to return the total number of these good triplets.

Intuition

The straightforward way to find all good triplets is to check every possible triplet in the array to see if it meets the criteria. This involves using three nested loops to generate all possible combinations of i, j, and k where 0 <= i < j < k < arr.length.

Within these loops, we will calculate the absolute differences between arr[i], arr[j], and arr[k] and check if they satisfy the conditions related to a, b, and c. If a triplet satisfies all these conditions, we increment a counter.

This method is a brute-force approach since it explores all possible triplets without any optimizations. It ensures that all triplets are checked and counted correctly, albeit at the expense of potentially higher computational time, especially for large arrays.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which type of traversal does breadth first search do?

Solution Approach

The implementation of the solution provided in the reference code uses the brute-force approach, which is a common pattern when dealing with problems that require us to explore all possible combinations of elements to find a particular set that satisfies certain conditions.

Algorithm steps:

  1. Initialize a counter ans to keep track of the number of good triplets found.
  2. Calculate the length n of the input array arr.
  3. Iterate over the array with the first pointer i, which runs from the beginning of the array to the third-to-last element.
  4. For each i, iterate with the second pointer j, which runs from one element after i to the second-to-last element.
  5. For each j, iterate with the third pointer k, which runs from one element after j to the last element.
  6. Inside the innermost loop (where k is iterating), check if the current triplet (arr[i], arr[j], arr[k]) is a good triplet by verifying the three conditions with the given a, b, and c:
    • abs(arr[i] - arr[j]) <= a
    • abs(arr[j] - arr[k]) <= b
    • abs(arr[i] - arr[k]) <= c
  7. If all three conditions are satisfied, increment the counter ans.
  8. After all iterations are complete, return the value of ans.

This approach does not use any specific data structures or complex algorithms, but rather relies on nested loops to examine each triplet one by one. The only operations involved are arithmetic operations (- and abs) and simple comparisons (<=).

While it is an exhaustive solution, it is not the most efficient in terms of time complexity. The time complexity of this approach is O(n^3), as there are three nested loops each iterating over the array. This solution can be quite slow for larger arrays but is perfectly fine for smaller input sizes where a more sophisticated algorithm might not lead to significant improvements in runtime or when fast and simple programming is required over an optimized, complex solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following:

  • arr = [2, 1, 3]
  • a = 1
  • b = 1
  • c = 1

Now we want to find the number of good triplets that satisfy all the given conditions.

We start by initializing our counter ans to 0. Our array length n is 3.

  1. We begin iterating with pointer i starting at 0.
  2. For i = 0 (arr[i] = 2), we move on to pointer j.
  3. We let j iterate starting from i + 1, which is 1.
  4. For j = 1 (arr[j] = 1), we then use pointer k.
  5. k starts iterating from j + 1, which is 2.
  6. For k = 2 (arr[k] = 3), we now check if (arr[i], arr[j], arr[k]) = (2, 1, 3) is a good triplet.
    • The absolute difference between arr[i] and arr[j] is |2 - 1| = 1, which is less than or equal to a.
    • The absolute difference between arr[j] and arr[k] is |1 - 3| = 2, so this is not less than or equal to b and we can ignore this triplet.

Since there are no other combinations to check, our count ans stays at 0. We conclude that there are no good triplets in the array [2, 1, 3] with the given a, b, and c values.

Applying the same approach in a larger array would involve more iterations, but the steps would be similar: iterate over each potential triplet and check if they satisfy the conditions.

Solution Implementation

1from typing import List  # Import List from typing module for type annotations.
2
3class Solution:
4    def count_good_triplets(self, arr: List[int], a: int, b: int, c: int) -> int:
5        # Initialize the count of good triplets.
6        good_triplets_count = 0
7      
8        # Get the length of the array.
9        array_length = len(arr)
10      
11        # Iterate through each element of the array for the first element of the triplet.
12        for first_index in range(array_length):
13            # For the second element, start from the next index of the first element.
14            for second_index in range(first_index + 1, array_length):
15                # For the third element, start from the next index of the second element.
16                for third_index in range(second_index + 1, array_length):
17                    # Check if the current triplet (arr[first_index], arr[second_index], arr[third_index]) 
18                    # is a good triplet based on the provided conditions.
19                    is_good_triplet = (
20                        abs(arr[first_index] - arr[second_index]) <= a and
21                        abs(arr[second_index] - arr[third_index]) <= b and
22                        abs(arr[first_index] - arr[third_index]) <= c
23                    )
24                    # If it is a good triplet, increment the good_triplets_count.
25                    good_triplets_count += is_good_triplet
26                  
27        # After checking all possible triplets, return the total count of good triplets.
28        return good_triplets_count
29
1class Solution {
2    public int countGoodTriplets(int[] arr, int maxDiffAB, int maxDiffBC, int maxDiffAC) {
3        // The length of the input array
4        int arrayLength = arr.length;
5        // Counter to keep track of the number of "good" triplets
6        int goodTripletsCount = 0;
7      
8        // Loop over each element for the first value of the triplet
9        for (int i = 0; i < arrayLength; ++i) {
10            // Loop over each element after the first value for the second value of the triplet
11            for (int j = i + 1; j < arrayLength; ++j) {
12                // Loop over each element after the second value for the third value of the triplet
13                for (int k = j + 1; k < arrayLength; ++k) {
14                    // Check the conditions to determine if the triplet (arr[i], arr[j], arr[k]) is "good"
15                    if (Math.abs(arr[i] - arr[j]) <= maxDiffAB && // Condition for the difference between arr[i] and arr[j]
16                        Math.abs(arr[j] - arr[k]) <= maxDiffBC && // Condition for the difference between arr[j] and arr[k]
17                        Math.abs(arr[i] - arr[k]) <= maxDiffAC) { // Condition for the difference between arr[i] and arr[k]
18                        // If all conditions are met, increment the count of "good" triplets
19                        ++goodTripletsCount;
20                    }
21                }
22            }
23        }
24        // Return the total number of "good" triplets found
25        return goodTripletsCount;
26    }
27}
28
1class Solution {
2public:
3    int countGoodTriplets(vector<int>& numbers, int limitA, int limitB, int limitC) {
4        int size = numbers.size(); // Size of the input array
5        int goodTripletsCount = 0; // Initialize count of good triplets
6
7        // Iterate over all possible triplets
8        for (int i = 0; i < size; ++i) {
9            for (int j = i + 1; j < size; ++j) {
10                // Check if the first condition is met to avoid unnecessary computations
11                if (abs(numbers[i] - numbers[j]) <= limitA) { 
12                    for (int k = j + 1; k < size; ++k) {
13                        // accumulate 1 to the count if all three conditions are satisfied
14                        goodTripletsCount += (abs(numbers[i] - numbers[j]) <= limitA &&
15                                              abs(numbers[j] - numbers[k]) <= limitB &&
16                                              abs(numbers[i] - numbers[k]) <= limitC) ? 1 : 0;
17                    }
18                }
19            }
20        }
21        // Return the total count of good triplets
22        return goodTripletsCount;
23    }
24};
25
1// Define the function to count good triplets
2function countGoodTriplets(numbers: number[], limitA: number, limitB: number, limitC: number): number {
3    let size = numbers.length; // Size of the input array
4    let goodTripletsCount = 0; // Initialize count of good triplets
5
6    // Iterate over all possible triplets
7    for (let i = 0; i < size; ++i) {
8        for (let j = i + 1; j < size; ++j) {
9            // Check if the first condition is met to avoid unnecessary computations
10            if (Math.abs(numbers[i] - numbers[j]) <= limitA) {
11                for (let k = j + 1; k < size; ++k) {
12                    // Increment the count if all three conditions are satisfied
13                    goodTripletsCount += (Math.abs(numbers[i] - numbers[j]) <= limitA &&
14                                          Math.abs(numbers[j] - numbers[k]) <= limitB &&
15                                          Math.abs(numbers[i] - numbers[k]) <= limitC) ? 1 : 0;
16                }
17            }
18        }
19    }
20    // Return the total count of good triplets
21    return goodTripletsCount;
22}
23
Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Time and Space Complexity

The given Python code implements a function to count the number of good triplets in an array. A triplet (arr[i], arr[j], arr[k]) is considered good if it satisfies all of the following conditions:

  • 0 <= i < j < k < arr.length
  • |arr[i] - arr[j]| <= a
  • |arr[j] - arr[k]| <= b
  • |arr[i] - arr[k]| <= c

Where |x - y| denotes the absolute value of the difference between x and y.

Time Complexity

The time complexity of the function is determined by the three nested for-loops. The outermost loop runs n times, where n is the length of the array. The middle loop runs up to n-1 times, and the innermost loop runs up to n-2 times. Therefore, the total number of iterations is governed by the series of descending integers starting from n and decreasing to 1.

The time complexity can then be calculated as the sum of the series Σ(i * (i-1) / 2), for i from 1 to n-2. This simplifies to O(n^3) since the loop counters are independent and the series is a sum of cubic numbers.

Space Complexity

The space complexity of the solution is O(1). Other than the input array, only a fixed number of integer variables (ans, n, i, j, k) are used, and their number does not depend on the input size n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫