We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Good Triplets in an Array

Difficulty: Hard

Problem Description

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. Return the total number of good triplets.

Key Insights

  • A good triplet (x, y, z) satisfies the condition that the indices of x, y, and z in both nums1 and nums2 are in strictly increasing order.
  • The problem can be reduced to counting combinations of triplets based on the positions of elements in both arrays.
  • Efficient counting can be achieved using data structures like Binary Indexed Trees or Segment Trees to maintain and query counts of valid indices.

Space and Time Complexity

Time Complexity: O(n^2 log n) in the worst case, but can be optimized to O(n log n) with appropriate data structures.
Space Complexity: O(n) for storing index positions and counts.

Solution

To solve the problem, we can follow these steps:

  1. Create two mappings to store the indices of elements in both nums1 and nums2.
  2. For each element, we will determine how many valid pairs can be formed with it as the last element of the triplet.
  3. Use a Binary Indexed Tree (BIT) to maintain the counts of valid previous elements as we iterate through the elements in increasing order.

Code Solutions

def countGoodTriplets(nums1, nums2):
    n = len(nums1)
    pos1 = {value: index for index, value in enumerate(nums1)}
    pos2 = {value: index for index, value in enumerate(nums2)}
    
    # Create a list of (pos1[v], pos2[v]) pairs for sorting
    pairs = [(pos1[v], pos2[v]) for v in range(n)]
    pairs.sort()  # Sort by pos1
    
    # BIT to count valid previous positions in pos2
    BIT = [0] * (n + 1)
    
    def update(index, value):
        while index <= n:
            BIT[index] += value
            index += index & -index
            
    def query(index):
        total = 0
        while index > 0:
            total += BIT[index]
            index -= index & -index
        return total
    
    count = 0
    
    # Iterate through sorted pairs to count good triplets
    for i in range(n):
        p1, p2 = pairs[i]
        
        # Count how many j's can be paired with the current i
        count += query(p2)  # Count of valid pairs before this p2
        
        # Update BIT with the current p2
        update(p2 + 1, 1)  # Use p2 + 1 because BIT is 1-indexed
    
    return count

# Example usage
print(countGoodTriplets([2,0,1,3], [0,1,2,3]))  # Output: 1
← Back to All Questions