Count Good Triplets in an Array

Hard

Walmart

0 views

Topics:

Arrays

You are given two 0-indexed arrays nums1 and nums2 of length n, both of which are permutations of [0, 1, ..., n - 1].

A good triplet is a set of 3 distinct values which are present in increasing order by position both in nums1 and nums2. In other words, if we consider pos1_v as the index of the value v in nums1 and pos2_v as the index of the value v in nums2, then a good triplet will be a set (x, y, z) where 0 <= x, y, z <= n - 1, such that pos1_x < pos1_y < pos1_z and pos2_x < pos2_y < pos2_z.

Return the total number of good triplets.

Example 1:

Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output: 1
Explanation: 
There are 4 triplets (x,y,z) such that pos1_x < pos1_y < pos1_z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3). 
Out of those triplets, only the triplet (0,1,3) satisfies pos2_x < pos2_y < pos2_z. Hence, there is only 1 good triplet.

Example 2:

Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
Output: 4
Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).

Constraints:

n == nums1.length == nums2.length
3 <= n <= 10⁵
0 <= nums1[i], nums2[i] <= n - 1
nums1 and nums2 are permutations of [0, 1, ..., n - 1].

Count Good Triplets in an Array

Hard

Walmart

0 views

Topics:

Arrays

You are given two 0-indexed arrays nums1 and nums2 of length n, both of which are permutations of [0, 1, ..., n - 1].

A good triplet is a set of 3 distinct values which are present in increasing order by position both in nums1 and nums2. In other words, if we consider pos1_v as the index of the value v in nums1 and pos2_v as the index of the value v in nums2, then a good triplet will be a set (x, y, z) where 0 <= x, y, z <= n - 1, such that pos1_x < pos1_y < pos1_z and pos2_x < pos2_y < pos2_z.

Return the total number of good triplets.

Example 1:

Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output: 1
Explanation: 
There are 4 triplets (x,y,z) such that pos1_x < pos1_y < pos1_z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3). 
Out of those triplets, only the triplet (0,1,3) satisfies pos2_x < pos2_y < pos2_z. Hence, there is only 1 good triplet.

Example 2:

Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
Output: 4
Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).

Constraints:

n == nums1.length == nums2.length
3 <= n <= 10⁵
0 <= nums1[i], nums2[i] <= n - 1
nums1 and nums2 are permutations of [0, 1, ..., n - 1].

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array, and what is the range of values for the integers within the array?
Are the values a, b, and c guaranteed to be non-negative integers?
If no 'good triplets' are found, what should the function return? Should it return 0, null, or throw an exception?
Can the input array contain duplicate numbers, and if so, how should they be handled when determining 'good triplets'?
Are the values of `a`, `b`, and `c` also guaranteed to be non-negative integers?

Brute Force Solution

Approach

The brute force method for counting good triplets is like exhaustively checking every possible combination of three numbers from a list. We look at each possible set of three numbers to see if they meet specific requirements. If they do, we count it as a good triplet.

Here's how the algorithm would work step-by-step:

Start by picking the very first number in the list.
Then, pick the second number from the list.
Next, pick a third number from the list, ensuring it is different from the first two.
Check if these three numbers satisfy all given conditions to be considered a "good" triplet.
If they do, add one to our running count of good triplets.
Repeat the process by picking a different third number, and checking the conditions again.
Continue this process until you have checked all possible third numbers for the first and second numbers you initially picked.
Now, pick a different second number from the list and repeat all the steps from picking the third number onwards.
After you've checked all possible second numbers, select a different first number and repeat the entire process from the second number onwards.
Keep repeating these steps until you have considered every possible combination of three numbers from the list.
Finally, return the total count of good triplets found.

Code Implementation

def count_good_triplets(array, a_threshold, b_threshold, c_threshold):
    list_length = len(array)
    good_triplet_count = 0

    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Ensure second index is after first

            for third_index in range(second_index + 1, list_length):
                # Third index must be after the second

                first_second_diff = abs(array[first_index] - array[second_index])
                second_third_diff = abs(array[second_index] - array[third_index])
                first_third_diff = abs(array[first_index] - array[third_index])

                # Check that the triplet meets all conditions
                if (first_second_diff <= a_threshold and
                        second_third_diff <= b_threshold and
                        first_third_diff <= c_threshold):
                    good_triplet_count += 1

    return good_triplet_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The provided solution iterates through all possible triplets in the input array. The outermost loop selects the first element, the middle loop selects the second element, and the innermost loop selects the third element, with each element's selection being dependent on the previous ones. Since we have three nested loops, each potentially iterating up to 'n' times where 'n' is the size of the array, the total number of operations grows proportionally to n * n * n. Therefore, the time complexity is O(n³).

Space Complexity

O(1) – The provided solution, based on the plain English explanation, exhaustively checks every possible triplet using nested loops. It does not use any auxiliary data structures like lists, hashmaps, or recursion. It only uses a few integer variables to keep track of the loop indices and the count of good triplets. Therefore, the space required remains constant regardless of the input array's size N, resulting in O(1) space complexity.

Optimal Solution

Approach

The brute-force method would check every possible triplet, which is slow. A much faster approach involves focusing on each number in the input and efficiently counting the valid triplets it can form part of by considering numbers before and after it.

Here's how the algorithm would work step-by-step:

For each number in the input, determine how many numbers *before* it satisfy the first condition of a valid triplet.
For each number in the input, also figure out how many numbers *after* it can satisfy the second and third conditions *given* that you already picked the number before it.
Combine the counts. For each number, multiply the number of valid 'before' numbers by the number of valid 'after' numbers to get the number of valid triplets that number can be a part of.
Sum up these triplet counts for every number in the input. This total is the final answer - the total number of good triplets.

Code Implementation

def count_good_triplets(array, first_threshold, second_threshold, third_threshold):
    array_length = len(array)
    good_triplet_count = 0

    for j in range(1, array_length - 1):
        # Count elements before array[j] that satisfy condition one.
        before_count = 0
        for i in range(j):
            if abs(array[i] - array[j]) <= first_threshold:
                before_count += 1

        # Count elements after array[j] that satisfy conditions two and three.
        after_count = 0
        for k in range(j + 1, array_length):
            if abs(array[j] - array[k]) <= second_threshold and abs(array[i] - array[k]) <= third_threshold:
                after_count += 1

        # Accumulate the number of good triplets found using array[j].
        good_triplet_count += before_count * after_count

    return good_triplet_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The solution iterates through each of the n elements in the input array. For each element, it iterates through the elements before it (to count the numbers satisfying the first condition), and then iterates through the elements after it (to count the numbers satisfying the second and third conditions). Thus, for each of the n elements, we perform operations proportional to n in the worst case, resulting in roughly n * n operations. Therefore, the overall time complexity is O(n²).

Space Complexity

O(1) – The algorithm's plain English explanation indicates that for each number in the input array, it counts numbers before and after that satisfy certain conditions. It does not mention any auxiliary data structures like lists, hash maps, or recursion. The operations appear to involve only a few constant-size variables for counting valid triplets, meaning the auxiliary space remains constant regardless of the input size N. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty as no triplets can be formed.
Array size less than 3	Return 0 if the array has fewer than 3 elements because a triplet cannot be formed.
Large array size with tight time constraints	Optimize the solution to avoid excessive nested loops (e.g., consider sorting or other data structures for efficiency).
Identical elements in the array	The solution should correctly count triplets even when the array contains duplicate elements at different indices.
a, b, or c are negative numbers	The absolute difference calculations must handle negative numbers correctly.
a, b, or c are zero	The absolute difference calculations should work fine with zero values.
Extreme values for a, b, c, a, b, or c that could cause integer overflow	Consider using larger data types (e.g., long) to avoid integer overflow when calculating absolute differences.
No good triplets exist in the input array	The solution should correctly return 0 when no triplets satisfy the given conditions.