2657. Find the Prefix Common Array of Two Arrays - Detailed Explanation

Problem Statement

Description:
You are given two 0-indexed integer arrays arr1 and arr2 of the same length. Both arrays are permutations of the numbers from 1 to n (i.e. each number appears exactly once in each array). For every index i from 0 to n - 1, define the prefix of an array as all the elements from index 0 to i. The goal is to return an array res of length n where:

• res[i] is the number of common elements between the prefix of arr1 and the prefix of arr2 up to index i.

Example 1:

• Input:
  arr1 = [1, 3, 2, 4]
  arr2 = [3, 1, 2, 4]

• Output:
  [0, 2, 3, 4]

• Explanation:

  • For i = 0:
    Prefixes: [1] and [3]
    Common elements: {} → count = 0
  • For i = 1:
    Prefixes: [1, 3] and [3, 1]
    Common elements: {1, 3} → count = 2
  • For i = 2:
    Prefixes: [1, 3, 2] and [3, 1, 2]
    Common elements: {1, 2, 3} → count = 3
  • For i = 3:
    Prefixes: [1, 3, 2, 4] and [3, 1, 2, 4]
    Common elements: {1, 2, 3, 4} → count = 4

Example 2:

• Input:
  arr1 = [2, 3, 1]
  arr2 = [1, 2, 3]

• Output:
  [0, 1, 3]

• Explanation:

  • For i = 0:
    Prefixes: [2] and [1]
    Common elements: {} → count = 0
  • For i = 1:
    Prefixes: [2, 3] and [1, 2]
    Common elements: {2} → count = 1
  • For i = 2:
    Prefixes: [2, 3, 1] and [1, 2, 3]
    Common elements: {1, 2, 3} → count = 3

Constraints:

• Both arr1 and arr2 have the same length n.
• Both arrays are permutations of [1, 2, …, n].
• 1 ≤ n ≤ (a value that allows for linear time solutions).

Hints Before You Code

• Hint 1:
  You can use data structures (like hash sets or boolean arrays) to track which numbers have appeared in each prefix. At each index, the number of common elements is simply the intersection of these two sets.

• Hint 2:
  For an efficient solution, update a running common count as you iterate over the arrays. Instead of computing the entire intersection every time, maintain two arrays (or sets) and update the count incrementally as new elements are encountered.

Approaches

Approach A: Using Sets and Intersection

Idea:

• Maintain two sets: one for the prefix of arr1 and one for the prefix of arr2.
• For each index i, add arr1[i] to the first set and arr2[i] to the second set.
• Compute the intersection of these two sets and record its size as res[i].

Pros:

• Conceptually simple and straightforward.

Cons:

• Recomputing the intersection at every index can lead to a time complexity of O(n²) in the worst-case scenario (if the number of elements in the sets grows linearly).

Pseudocode:

def findPrefixCommonArray(arr1, arr2):
    set1, set2 = set(), set()
    result = []
    for i in range(len(arr1)):
        set1.add(arr1[i])
        set2.add(arr2[i])
        result.append(len(set1 & set2))  # Compute intersection size
    return result

Approach B: Optimized Incremental Update with Boolean Arrays

Idea:

• Since both arrays are permutations of numbers from 1 to n, use boolean arrays (seenA and seenB) of size n+1 to track whether a number has appeared in arr1 and arr2.
• Maintain a running counter commonCount which increments whenever a number is marked as seen in both arrays for the first time.
• For each index i, update the seen arrays and adjust commonCount accordingly. Append commonCount to the result.

Key Points:

• Process each index once and update in constant time.
• When processing an element from arr1, if it has already been seen in arr2, then that number becomes common.
• Similarly, when processing an element from arr2, if it has already been seen in arr1, then it becomes common.
• If both arrays have the same element at index i (i.e. arr1[i] == arr2[i]), it is counted only once.

Pseudocode:

def findPrefixCommonArray(arr1, arr2):
    n = len(arr1)
    seenA = [False] * (n + 1)
    seenB = [False] * (n + 1)
    commonCount = 0
    result = []
    for i in range(n):
        a = arr1[i]
        b = arr2[i]
        if not seenA[a]:
            seenA[a] = True
            if seenB[a]:
                commonCount += 1
        if not seenB[b]:
            seenB[b] = True
            if seenA[b]:
                commonCount += 1
        result.append(commonCount)
    return result

Time Complexity: O(n)
Space Complexity: O(n)

Step-by-Step Walkthrough (Optimized Approach)

Consider arr1 = [1, 3, 2, 4] and arr2 = [3, 1, 2, 4].

1. Initialization:

   • Create boolean arrays seenA and seenB of length 5 (since n = 4).
   • Set commonCount = 0 and initialize an empty result list.

2. Iteration 0 (i = 0):

   • a = 1, b = 3
   • Mark seenA[1] as true.
     Since seenB[1] is false, commonCount remains 0.
   • Mark seenB[3] as true.
     Since seenA[3] is false, commonCount remains 0.
   • Result: [0]

3. Iteration 1 (i = 1):

   • a = 3, b = 1
   • For a = 3:
     seenA[3] is false; mark it true.
     Now, seenB[3] is true (from previous iteration) so increment commonCount to 1.
   • For b = 1:
     seenB[1] is false; mark it true.
     Now, seenA[1] is true so increment commonCount to 2.
   • Result: [0, 2]

4. Iteration 2 (i = 2):

   • a = 2, b = 2
   • For a = 2:
     Mark seenA[2] as true; since seenB[2] is false, no change.
   • For b = 2:
     Mark seenB[2] as true; now seenA[2] is true so increment commonCount to 3.
   • Result: [0, 2, 3]

5. Iteration 3 (i = 3):

   • a = 4, b = 4
   • For a = 4:
     Mark seenA[4] as true; since seenB[4] is false, no change.
   • For b = 4:
     Mark seenB[4] as true; now seenA[4] is true so increment commonCount to 4.
   • Result: [0, 2, 3, 4]

Code Implementations

Python Implementation