LeetCode 2657 - Find the Prefix Common Array of Two Arrays

The problem provides two arrays, A and B, each a permutation of integers from 1 to n. A permutation means each number from 1 to n appears exactly once in the array.

leetcodemediumarrayhash-tablebit-manipulation

LeetCode Problem 2657

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Bit Manipulation

Solution

Problem Understanding

The problem provides two arrays, A and B, each a permutation of integers from 1 to n. A permutation means each number from 1 to n appears exactly once in the array. We are asked to compute a new array C, called the prefix common array, where C[i] represents the number of elements that appear in both A and B up to index i.

In simpler terms, for each position i, we look at the first i + 1 elements of both A and B and count how many numbers are present in both slices. The constraints ensure that n is at most 50, so solutions with quadratic time complexity are acceptable but we can optimize further.

Important edge cases include small arrays of length 1, arrays where elements align perfectly, or arrays where common elements appear late in the sequences. The problem guarantees no repeated elements and consistent lengths, so we do not need to handle invalid inputs.

Approaches

The brute-force approach is straightforward. For each index i, we extract the first i + 1 elements of both arrays and compute the intersection. The count of this intersection is then stored in C[i]. While correct, this approach is inefficient because each intersection operation scans up to i + 1 elements, resulting in O(n^2) time complexity.

The optimal approach leverages the fact that A and B are permutations of 1 to n. We can use a frequency array (or a hash set) to track which numbers have appeared in either array. As we iterate through A and B simultaneously, we update counts for each number. When a number appears for the second time (meaning it has appeared in both arrays), we increment the running count for C[i]. This approach achieves O(n) time complexity and O(n) space complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Count intersection for each prefix directly
Optimal O(n) O(n) Track number occurrences and increment count when seen in both arrays

Algorithm Walkthrough

  1. Initialize an array C of length n to store the prefix common counts, all values initially zero.
  2. Initialize a frequency array or dictionary count_map to track the number of times each number has appeared in either array.
  3. Initialize a variable common_count to 0. This keeps track of numbers that have appeared in both arrays up to the current index.
  4. Iterate over indices i from 0 to n - 1. At each step:

a. Increment the count for A[i] in count_map. If its count becomes 2, increment common_count.

b. Increment the count for B[i] in count_map. If its count becomes 2, increment common_count.

c. Assign C[i] = common_count. 5. Return the array C.

Why it works: By tracking how many times each number has appeared and updating the count only when a number has appeared in both arrays, the algorithm maintains an accurate running total of common elements for each prefix. The frequency array acts as a persistent record, eliminating repeated scans of prefixes.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        C = [0] * n
        count_map = defaultdict(int)
        common_count = 0
        
        for i in range(n):
            count_map[A[i]] += 1
            if count_map[A[i]] == 2:
                common_count += 1
            
            count_map[B[i]] += 1
            if count_map[B[i]] == 2:
                common_count += 1
            
            C[i] = common_count
        
        return C

The Python implementation uses a defaultdict to automatically initialize counts to zero. We iterate once over the arrays, updating counts for A[i] and B[i]. Whenever a number’s count reaches 2, it has appeared in both arrays, and we update common_count. This running total is stored in C[i].

Go Solution

func findThePrefixCommonArray(A []int, B []int) []int {
    n := len(A)
    C := make([]int, n)
    countMap := make([]int, n+1)
    commonCount := 0

    for i := 0; i < n; i++ {
        countMap[A[i]]++
        if countMap[A[i]] == 2 {
            commonCount++
        }

        countMap[B[i]]++
        if countMap[B[i]] == 2 {
            commonCount++
        }

        C[i] = commonCount
    }

    return C
}

The Go version uses a slice countMap of length n+1 because numbers range from 1 to n, avoiding the need for a hash map. The logic mirrors the Python implementation. No nil checks are necessary since slices are initialized to zero values.

Worked Examples

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

i A[i] B[i] Seen in both C[i]
0 1 3 {} 0
1 3 1 {1,3} 2
2 2 2 {1,2,3} 3
3 4 4 {1,2,3,4} 4

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

i A[i] B[i] Seen in both C[i]
0 2 3 {} 0
1 3 1 {3} 1
2 1 2 {1,2,3} 3

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through arrays once, updating counts in O(1) per element
Space O(n) We maintain a count map of size n+1 to track occurrences

The algorithm scales linearly with the length of the arrays, and extra space is proportional to n.

Test Cases

# Provided examples
assert Solution().findThePrefixCommonArray([1,3,2,4], [3,1,2,4]) == [0,2,3,4]  # Example 1
assert Solution().findThePrefixCommonArray([2,3,1], [3,1,2]) == [0,1,3]      # Example 2

# Edge cases
assert Solution().findThePrefixCommonArray([1], [1]) == [1]                    # Single element
assert Solution().findThePrefixCommonArray([1,2,3], [1,2,3]) == [1,2,3]      # Perfect match
assert Solution().findThePrefixCommonArray([3,2,1], [1,2,3]) == [0,1,3]      # Reverse order
assert Solution().findThePrefixCommonArray([1,2,3,4,5], [5,4,3,2,1]) == [0,0,1,3,5] # Partial overlaps
Test Why
[1,3,2,4], [3,1,2,4] Verifies multiple common elements appear gradually
[2,3,1], [3,1,2] Checks common elements appear out of order
[1], [1] Single-element edge case
[1,2,3], [1,2,3] Arrays match exactly
[3,2,1], [1,2,3] Reverse ordering
[1,2,3,4,5], [5,4,3,2,1] Partial overlaps and scattered matches

Edge Cases

Single-element arrays: If A and B have length 1, the only element may or may not match. The algorithm correctly counts a match when the only element appears in both arrays.

Reverse permutations: When A and B are in reverse order, common elements appear later. A naive prefix intersection might miscount if it assumes ordering, but the count-based approach correctly tracks elements independently of order.

No common elements in early prefixes: Early prefixes might have no common numbers. The algorithm initializes common_count to zero and only increments when a number is seen in both arrays, ensuring accurate counts from the first index onward.