Find the Prefix Common Array of Two Arrays

Medium
1172.

Find the Prefix Common Array of Two Arrays

Find the Prefix Common Array of Two Arrays is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Google interviews.

a and b are both permutations of the integers 1 to n. Their prefix common array is the array c of length n where c[i] is the number of values that appear in both a[0..i] and b[0..i].

Return c.

Example 1

Input
a = [2,4,1,3], b = [4,1,2,3]
Output
[0,1,3,4]
Explanation
After index 1 only `4` is shared; after index 2 the prefixes hold `{1,2,4}` each.

Example 2

Input
a = [3,1,2], b = [3,2,1]
Output
[1,1,3]

Constraints

  • 1 <= a.length == b.length == n <= 50
  • 1 <= a[i], b[i] <= n
  • a and b are permutations of 1..n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} a
 * @param {number[]} b
 * @return {number[]}
 */
var findThePrefixCommonArray = function(a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Prefix Common Array of Two Arrays — Solution

Find the Prefix Common Array of Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Prefix Common Array of Two Arrays is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Google interviews.

Problem statement

a and b are both permutations of the integers 1 to n. Their prefix common array is the array c of length n where c[i] is the number of values that appear in both a[0..i] and b[0..i].

Return c.

Example 1

Input: a = [2,4,1,3], b = [4,1,2,3]
Output: [0,1,3,4]
Explanation: After index 1 only `4` is shared; after index 2 the prefixes hold `{1,2,4}` each.

Example 2

Input: a = [3,1,2], b = [3,2,1]
Output: [1,1,3]

Constraints

  • 1 <= a.length == b.length == n <= 50
  • 1 <= a[i], b[i] <= n
  • a and b are permutations of 1..n

Hints for Find the Prefix Common Array of Two Arrays

  1. Hint 1

    Recomputing the intersection for every prefix is O(n²) — fine for these limits, but there is a one-pass way.

  2. Hint 2

    Each value appears once in each array, so it becomes common exactly when its second occurrence (in either array) has been seen.

  3. Hint 3

    Keep a count per value; when a count reaches 2, the number of common values grows by one.

How to solve Find the Prefix Common Array of Two Arrays

A value joins the common set at the moment both arrays have shown it — that is, the second time it is seen across the two prefixes. Counting sightings per value turns the prefix intersection into a running counter.

Approach

  1. Keep seen[v] for v = 1..n, all 0, and common = 0.
  2. For each i: increment seen[a[i]]; if it became 2, increment common.
  3. Do the same for b[i].
  4. Set c[i] = common.

Why it works

Within one permutation a value occurs once, so seen[v] = 2 means v is in both prefixes, and that transition happens exactly once per value, at the first index where both prefixes contain it. Hence common always equals the size of the intersection.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Process both a[i] and b[i] before recording c[i] — when a[i] == b[i] the value counts at index i.
  • The answer is non-decreasing and ends at n; a quick sanity check.
  • A bitmask (n <= 50 fits in 64 bits) also works, but the counting array is simpler.

Reference solution

Python

from typing import List

def findThePrefixCommonArray(a: List[int], b: List[int]) -> List[int]:
    n = len(a)
    seen = [0] * (n + 1)
    common = 0
    res = []
    for i in range(n):
        seen[a[i]] += 1
        if seen[a[i]] == 2:
            common += 1
        seen[b[i]] += 1
        if seen[b[i]] == 2:
            common += 1
        res.append(common)
    return res

Java

public static int[] findThePrefixCommonArray(int[] a, int[] b) {
    int n = a.length;
    int[] seen = new int[n + 1];
    int[] res = new int[n];
    int common = 0;
    for (int i = 0; i < n; i++) {
        if (++seen[a[i]] == 2) common++;
        if (++seen[b[i]] == 2) common++;
        res[i] = common;
    }
    return res;
}

C++

vector<int> findThePrefixCommonArray(vector<int>& a, vector<int>& b) {
    int n = a.size();
    vector<int> seen(n + 1, 0), res(n);
    int common = 0;
    for (int i = 0; i < n; i++) {
        if (++seen[a[i]] == 2) common++;
        if (++seen[b[i]] == 2) common++;
        res[i] = common;
    }
    return res;
}

JavaScript

var findThePrefixCommonArray = function(a, b) {
    var n = a.length;
    var seen = new Array(n + 1).fill(0);
    var common = 0, res = [];
    for (var i = 0; i < n; i++) {
        if (++seen[a[i]] === 2) common++;
        if (++seen[b[i]] === 2) common++;
        res.push(common);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets