Find the prefix common array of two arrays

Array Hash Table Bit Manipulation

87.0% acceptance

Feb 25, 2026

1154

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
    let n = a.len();
    let mut seen_a = vec![false; n + 1];
    let mut seen_b = vec![false; n + 1];
    let mut common = 0i32;
    let mut result = Vec::with_capacity(n);

    for i in 0..n {
      seen_a[a[i] as usize] = true;
      seen_b[b[i] as usize] = true;

      // Count new common elements at this step
      // a[i] is now visible in A; if it's also in B, increment
      if seen_b[a[i] as usize] { common += 1; }
      // b[i] is now visible in B; if it's also in A and it's not the same as a[i], increment
      if seen_a[b[i] as usize] && b[i] != a[i] { common += 1; }

      result.push(common);
    }
    result
  }
}