#2657

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Prefix Common Array of Two Arrays

This problem challenges you to find the prefix common array of two integer permutations, utilizing array scanning and hash lookup techniques.

array hash table bit manipulation

Problem Statement

You are given two 0-indexed integer permutations A and B of length n. Your task is to return the prefix common array C of A and B. The array C should have the property that C[i] equals the count of numbers that appear at or before index i in both A and B.

For example, if A = [1, 3, 2, 4] and B = [3, 1, 2, 4], the output C will be [0, 2, 3, 4]. At each index i, count the common elements in A and B up to that point. Consider optimizing this using a hash table to track the occurrences efficiently.

Examples

Example 1

Input: A = [1,3,2,4], B = [3,1,2,4]

Output: [0,2,3,4]

At i = 0: no number is common, so C[0] = 0. At i = 1: 1 and 3 are common in A and B, so C[1] = 2. At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3. At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2

Input: A = [2,3,1], B = [3,1,2]

Output: [0,1,3]

At i = 0: no number is common, so C[0] = 0. At i = 1: only 3 is common in A and B, so C[1] = 1. At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.

Solution Approach

Array Scanning with Hash Lookup

To solve this problem, you can iterate over both arrays, using a hash table to track the occurrences of numbers in the arrays. As you traverse the arrays, update the count of common elements at each index by comparing the frequency of numbers from both arrays.

Efficient Count Tracking

Keep a frequency array to store the number of times each integer appears in both arrays up to index i. This allows for constant time lookups and helps you efficiently build the prefix common array without repeatedly checking the entire array.

Incremental Construction of the Result

At each step, update the prefix common array by incrementing the common count whenever a number appears in both A and B. This approach ensures that you only need to traverse each array once, maintaining an O(n) time complexity.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because we traverse each array only once, and the hash table lookup operations are O(1) on average. The space complexity is O(n) as we maintain the frequency counts for each number in the arrays up to index i.

What Interviewers Usually Probe

The candidate demonstrates an understanding of array scanning and hash lookup.
The candidate considers the importance of efficient tracking using a frequency array.
The candidate proposes an optimal solution with clear handling of edge cases.

Common Pitfalls or Variants

Common pitfalls

Failing to properly track the frequency of numbers in both arrays, leading to incorrect results.
Overcomplicating the solution with nested loops instead of using efficient hash lookups.
Not considering the constraints and trying to use less efficient approaches with higher time complexity.

Follow-up variants

What if the arrays were not permutations and contained duplicates? How would the approach change?
Can the algorithm be optimized further for larger array sizes? Consider techniques like early termination.
What if the problem were extended to find common prefixes for more than two arrays?

FAQ

How does the array scanning approach work in this problem?

Array scanning helps you evaluate each index in both arrays, incrementally counting common elements. This approach ensures the solution is efficient and avoids unnecessary rechecking of elements.

What is the time complexity of the solution?

The time complexity of the solution is O(n), where n is the length of the input arrays. This is due to the single pass over the arrays and constant-time hash table lookups.

Why is using a hash table important in this problem?

A hash table is crucial for efficiently tracking the frequency of numbers in both arrays, allowing for constant time lookups and avoiding repeated iterations over the arrays.

Can this solution be optimized for larger arrays?

For very large arrays, optimizing space and time complexity can involve early termination or other advanced techniques, but for arrays of size n <= 50, this solution is efficient.

What are some common pitfalls in solving this problem?

Common pitfalls include failing to track the frequency of numbers correctly, overcomplicating the solution with unnecessary nested loops, or ignoring the problem's constraints.

terminal

Solution

Solution 1: Counting

We can use two arrays $cnt1$ and $cnt2$ to record the occurrence times of each element in arrays $A$ and $B$ respectively, and use an array $ans$ to record the answer.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        cnt1 = Counter()
        cnt2 = Counter()
        for a, b in zip(A, B):
            cnt1[a] += 1
            cnt2[b] += 1
            t = sum(min(v, cnt2[x]) for x, v in cnt1.items())
            ans.append(t)
        return ans

Solution 2: Bit Operation (XOR Operation)

We can use an array $vis$ of length $n+1$ to record the occurrence situation of each element in arrays $A$ and $B$, the initial value of array $vis$ is $1$. In addition, we use a variable $s$ to record the current number of common elements.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        cnt1 = Counter()
        cnt2 = Counter()
        for a, b in zip(A, B):
            cnt1[a] += 1
            cnt2[b] += 1
            t = sum(min(v, cnt2[x]) for x, v in cnt1.items())
            ans.append(t)
        return ans

Solution 3: Bit Manipulation (Space Optimization)

Since the elements of arrays $A$ and $B$ are in the range $[1, n]$ and do not exceed $50$, we can use an integer $x$ and an integer $y$ to represent the occurrence of each element in arrays $A$ and $B$, respectively. Specifically, we use the $i$-th bit of integer $x$ to indicate whether element $i$ has appeared in array $A$, and the $i$-th bit of integer $y$ to indicate whether element $i$ has appeared in array $B$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        cnt1 = Counter()
        cnt2 = Counter()
        for a, b in zip(A, B):
            cnt1[a] += 1
            cnt2[b] += 1
            t = sum(min(v, cnt2[x]) for x, v in cnt1.items())
            ans.append(t)
        return ans

Continue Practicing

#2588 count the number of beautiful subarrays #2732 find a good subset of the matrix #2564 substring xor queries