Find the Prefix Common Array of Two Arrays

Find the Prefix Common Array of Two Arrays - Problem

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

Input & Output

Example 1 — Basic Case

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

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

💡 Note: At index 0: A[0]=1, B[0]=3, no common elements → 0. At index 1: A[0:1]=[1,3], B[0:1]=[3,1], common=[1,3] → 2. At index 2: A[0:2]=[1,3,2], B[0:2]=[3,1,2], common=[1,2,3] → 3. At index 3: A[0:3]=[1,3,2,4], B[0:3]=[3,1,2,4], common=[1,2,3,4] → 4.

Example 2 — Same Elements Different Order

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

› Output: [0,0,3]

💡 Note: At index 0: A[0]=2, B[0]=3, no common → 0. At index 1: A[0:1]=[2,3], B[0:1]=[3,1], common=[3] but we need both → 0 (only 3 is common). At index 2: A[0:2]=[2,3,1], B[0:2]=[3,1,2], all elements are now common → 3.

Example 3 — Minimum Size

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

› Output: [0,2]

💡 Note: At index 0: A[0]=1, B[0]=2, no common elements → 0. At index 1: A[0:1]=[1,2], B[0:1]=[2,1], both elements are common → 2.

Constraints

1 ≤ A.length == B.length ≤ 1000
1 ≤ A[i], B[i] ≤ A.length
A and B are permutations of integers from 1 to A.length

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two permutation arrays A and B of same length

Process Prefixes

At each index, count common elements in prefixes A[0:i] and B[0:i]

Result Array

Array C where C[i] = count of common elements up to index i

Key Takeaway

🎯 Key Insight: Use a frequency counter to detect when elements appear in both array prefixes - when frequency reaches 2, the element becomes common.

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use a frequency counter to track when elements become common between prefixes. The optimal approach uses a single pass with O(n) time and O(n) space, incrementing a counter whenever an element's frequency reaches 2 (meaning it appears in both arrays' prefixes).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(n)	For each position, check all previous elements in both arrays to count common ones
Two Pass with Hash Maps	O(n)	O(n)	Track elements as we encounter them, incrementing count when same element appears in both arrays
Optimized Single Pass	O(n)	O(n)	Track when elements become common by incrementing counter when same element appears in both arrays at current position

Brute Force — Algorithm Steps

For each index i from 0 to n-1
Collect all elements from A[0] to A[i] in a set
Count how many elements from B[0] to B[i] exist in that set

Visualization

Tap to expand

Step-by-Step Walkthrough

Position 0

Check A[0] and B[0] for common elements

Position 1

Check A[0:1] and B[0:1] for common elements

Continue

Repeat for each position, scanning all previous elements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* A, int* B, int n, int* returnSize) {
    *returnSize = n;
    int* result = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        // Create a simple array to track seen elements (since permutation of 1 to n)
        int* seen = (int*)calloc(n + 1, sizeof(int));
        
        // Mark elements from A[0] to A[i]
        for (int k = 0; k <= i; k++) {
            seen[A[k]] = 1;
        }
        
        // Count elements from B[0] to B[i] that are marked
        int count = 0;
        for (int j = 0; j <= i; j++) {
            if (seen[B[j]]) {
                count++;
            }
        }
        
        result[i] = count;
        free(seen);
    }
    
    return result;
}

int main() {
    char line[1000];
    
    // Read and parse A
    fgets(line, sizeof(line), stdin);
    int A[100], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        A[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Read and parse B
    fgets(line, sizeof(line), stdin);
    int B[100];
    token = strtok(line + 1, ",]");
    int idx = 0;
    while (token != NULL && idx < n) {
        B[idx++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(A, B, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n positions, we scan up to n elements to build sets and count matches

⚠ Quadratic Growth

Space Complexity

O(n)

Temporary set to store elements from prefix of A at each iteration

⚡ Linearithmic Space

29.8K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler