Find the Prefix Common Array of Two Arrays

medium array hash table bit manipulation

Problem

You are given two 0-indexed integer permutations A and B of length n (each contains every integer from 1 to n exactly once). Build the prefix common array C, where C[i] is the count of values that appear at or before index i in both A and B. Return C.

InputA = [1,3,2,4], B = [3,1,2,4]

Output[0,2,3,4]

At i=1 the prefixes {1,3} and {3,1} share both 1 and 3, so C[1]=2. By i=3 every value 1..4 has appeared in both, so C[3]=4.

A (permutation, comma-separated)

B (permutation, comma-separated)

def findThePrefixCommonArray(A, B):
    n = len(A)
    freq = [0] * (n + 1)   # freq[v] = how many prefixes hold v
    common = 0
    C = []
    for i in range(n):
        for v in (A[i], B[i]):
            freq[v] += 1
            if freq[v] == 2:   # now in BOTH prefixes
                common += 1
        C.append(common)
    return C

function findThePrefixCommonArray(A, B) {
  const n = A.length;
  const freq = new Array(n + 1).fill(0); // freq[v] = prefixes holding v
  let common = 0;
  const C = [];
  for (let i = 0; i < n; i++) {
    for (const v of [A[i], B[i]]) {
      freq[v] += 1;
      if (freq[v] === 2) common += 1; // now in BOTH prefixes
    }
    C.push(common);
  }
  return C;
}

int[] findThePrefixCommonArray(int[] A, int[] B) {
    int n = A.length;
    int[] freq = new int[n + 1];   // freq[v] = prefixes holding v
    int common = 0;
    int[] C = new int[n];
    for (int i = 0; i < n; i++) {
        for (int v : new int[]{A[i], B[i]}) {
            freq[v]++;
            if (freq[v] == 2) common++; // now in BOTH prefixes
        }
        C[i] = common;
    }
    return C;
}

vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
    int n = A.size();
    vector<int> freq(n + 1, 0);   // freq[v] = prefixes holding v
    int common = 0;
    vector<int> C;
    for (int i = 0; i < n; i++) {
        for (int v : {A[i], B[i]}) {
            freq[v]++;
            if (freq[v] == 2) common++; // now in BOTH prefixes
        }
        C.push_back(common);
    }
    return C;
}

Explanation

The naive idea is to rebuild two sets for every prefix and intersect them, which is O(n²). The key observation lets us do it in one linear pass with a small frequency table.

Because A and B are permutations, each value 1..n appears exactly once in each array. So as we extend the prefix one index at a time, a value can be counted at most once from A and once from B. Keep freq[v] = how many of the two prefixes currently contain v.

At index i we reveal two new entries, A[i] and B[i]. Increment freq for each. The instant a value's frequency reaches 2, it is present in both prefixes for the first time, so it just became common — bump a running common counter. A value never crosses 2 a second time, so the counter is exactly the size of the intersection.

Append common to C after processing each index. That single counter, updated incrementally, replaces all the per-prefix set work.

Bit-manipulation variant: represent each prefix as a bitmask — set bit v when value v appears. After index i the common values are exactly the bits set in maskA & maskB, so C[i] = popcount(maskA & maskB). With n ≤ 50 a 64-bit integer (or Python's big ints) holds the whole mask, giving an elegant O(n) solution that motivates this problem's Bit Manipulation tag.

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