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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Prefix Common Array of Two Arrays

Number: 2766

Difficulty: Medium

Paid? No

Companies: Google, Yandex, Meta, Amazon

Problem Description

Given two 0-indexed integer permutations A and B of length n, compute the prefix common array C such that C[i] is equal to the count of numbers that have appeared at or before index i in both A and B.

Key Insights

  • Both A and B are permutations containing all integers from 1 to n.
  • As you traverse both arrays, you can keep track of seen elements using sets.
  • The count at each index is determined by the intersection of the sets of elements seen so far in A and B.
  • Since n is small (up to 50), iterating over the sets to count common elements is efficient.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario because of the intersection counting at each step, but with n <= 50, this is acceptable. Space Complexity: O(n) for storing seen elements.

Solution

We maintain two sets: one for elements seen in A and one for elements seen in B. For each index i, we add the current element from A to the first set and the current element from B to the second set. Then, we calculate the number of common elements by computing the intersection of these sets. This intersection count is appended to the result array C. This method uses straightforward set operations to determine the common elements at every prefix.

Code Solutions

# Python solution for finding the prefix common array

def findThePrefixCommonArray(A, B):
    # Initialize result list and sets for seen elements in A and B
    common_prefix = []
    seen_A = set()
    seen_B = set()
    
    # Iterate over each index of the arrays
    for i in range(len(A)):
        # Add the current elements to their corresponding sets
        seen_A.add(A[i])
        seen_B.add(B[i])
        
        # Count the common elements in both sets
        common_count = len(seen_A & seen_B)
        
        # Append the count to the result list
        common_prefix.append(common_count)
        
    return common_prefix

# Example usage:
print(findThePrefixCommonArray([1, 3, 2, 4], [3, 1, 2, 4]))
← Back to All Questions