2657. Find the Prefix Common Array of Two Arrays

MediumArrayHash Table

Problem Description

In this problem, you are given two integer arrays A and B, both of which are permutations of integers from 1 to n (inclusive), representing that they include all integers within this range without repeats. This means each number from 1 through n appears exactly once in both arrays, but the order of numbers might differ between A and B.

The task is to construct a new array C, referred to as the "prefix common array," where each C[i] represents the total count of numbers that are present both in the A array and the B array up to the index i (including i itself). In other words, at each index i, you count how many numbers from both A[0...i] and B[0...i] have been encountered thus far and represent the same set.

The goal is to return this "prefix common array" C by comparing elements at corresponding indices of the given permutations A and B.

Intuition

The solution builds upon the idea of incrementally computing the intersection count of numbers between two permutations A and B up to a certain index. Since A and B are permutations of the same length containing all numbers from 1 through n, we know that every number will eventually appear.

The approach uses two counters, cnt1 and cnt2, to track the frequency of numbers appeared in A and B, respectively, as we go through the arrays. It employs a for loop to go through A and B simultaneously with the help of the zip function. At every step of this loop, we increment the count of the respective current number from A in cnt1 and from B in cnt2.

After updating the counts, we calculate the intersection up to the current index by iterating over the keys (which represent unique numbers) in cnt1. For each key x in cnt1, we determine the minimum occurrence value between cnt1[x] and cnt2[x], because commonality requires the number to appear in both permutations up to the current index, and its count in the common prefix array will be the minimum of the its occurrences in A and B so far.

Adding these minimum values together gives the total count of common numbers up to index i, which gets appended to the array ans. The process repeats for each index, finally leading to a complete ans array that acts as the required "prefix common array."

The key to this solution is recognizing that even though the order of elements in A and B is different, we can track common elements by counting occurrences up to the current index. And since each element is unique and will appear exactly once in the arrays, we avoid over-counting any number.

Solution Approach

The implementation of the solution follows a step-by-step approach to build the "prefix common array" ans progressively by iterating through the permutations A and B. Here's how the algorithm unfolds:

Initialization: Create empty lists ans, cnt1, and cnt2. Here, ans will store the final response, being the "prefix common array". cnt1 and cnt2 are counters in the form of dictionaries (from the collections module in Python) that will keep track of the frequency of each number in A and B, respectively.
Simultaneous Traversal: Using the zip() function to simultaneously iterate over both A and B. The zip() function pairs the items of A and B with the same indices together so that they can be processed in pairs.
Count Incrementation: On each iteration of the for loop, for the current elements a from A and b from B, the algorithm updates cnt1[a] and cnt2[b]. This action increments the counts of the elements within our counters cnt1 and cnt2, corresponding to the number of occurrences so far.
Calculating Intersection: After incrementing the occurrence counts for the latest elements, the next task is to compute the intersection size. The algorithm uses a comprehension together with the sum() function to calculate the sum of minimum counts for each unique number that has appeared up to the current index i. The minimum is taken between cnt1[x] and cnt2[x] for each number x, meaning the number of times x has appeared in both A and B up to i.
Appending to ans: The value calculated in the previous step reflects the total count of common numbers at index i in the permutations. This value is appended to the ans list.
Iterate Until the End: Repeat steps 3 to 5 until the algorithm reaches the end of the arrays A and B.
Return Result: After the loop terminates, the ans list, which contains the prefix intersection size at each index, is returned as it represents the solution to the problem.

The algorithm efficiently computes the intersection sizes using dictionary-based counters, offering a dynamic approach to tracking the elements as we traverse the permutations. The use of a for loop along with zip() ensures that we are always comparing the correct pair of elements from A and B with the corresponding index. Summing the minimum counts allows us to directly calculate the size of the intersection up to each index.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have two integer arrays A and B which are permutations of integers from 1 to 3:

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

We want to build the prefix common array C. Let's go step by step:

Initialization: We create empty ans, cnt1, and cnt2 lists/dictionaries.
Simultaneous Traversal: We begin iterating over both A and B using the zip() function.
Count Incrementation for index 0:
- We start with the first elements in A and B, which are 1 and 2.
- We increment cnt1[1] and cnt2[2].
- Now, cnt1 = {1: 1} and cnt2 = {2: 1}.
Calculating Intersection:
- We determine the minimum count for each number that has appeared.
- So far, 1 has not appeared in B and 2 has not appeared in A, thus the common count is 0.
- We append 0 to ans.
Appending to ans:
- Now, ans = [0].
Continue Traversal for index 1:
- Now we take the second elements 3 from A and 1 from B.
- We increment cnt1[3] and cnt2[1].
- Now, cnt1 = {1: 1, 3: 1} and cnt2 = {2: 1, 1: 1}.
Calculating Intersection:
- At this point, 1 is the only common number appearing in both A and B.
- We append the common count 1 to ans.
Appending to ans:
- Now, ans = [0, 1].
Final Traversal for index 2:
- For the last element, we have 2 from A and 3 from B.
- We update cnt1[2] and cnt2[3].
- Now, cnt1 = {1: 1, 3: 1, 2: 1} and cnt2 = {2: 1, 1: 1, 3: 1}.
Calculating Intersection:
- Each number has appeared once in both A and B.
- The total common count is the sum of occurrences of each number, which is 3.
Appending to ans:
- Finally, ans = [0, 1, 3].
Return Result:
- We have finished iterating through both arrays, and the completed ans list is [0, 1, 3].
- This ans list is the prefix common array C that we wanted to construct.

By following these steps, we built the prefix common array for permutations A and B using the algorithm. Each element of ans indicates the intersection size of A and B up to that index, which fulfills the goal of the problem.

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def findThePrefixCommonArray(self, array_1: List[int], array_2: List[int]) -> List[int]:
6        # Initialize the result list to store the common prefix counts
7        result = []
8      
9        # Create two Counter objects to keep track of the counts of elements
10        # in array_1 and array_2, respectively
11        count_1 = Counter()
12        count_2 = Counter()
13      
14        # Iterate through both arrays simultaneously using zip
15        # This will process the arrays as pairs of elements (a, b)
16        for a, b in zip(array_1, array_2):
17            # Increment the count of the current element 'a' in array_1's counter
18            count_1[a] += 1
19            # Increment the count of the current element 'b' in array_2's counter
20            count_2[b] += 1
21          
22            # Calculate the total number of common elements by iterating through each 
23            # element in the first array's counter and summing up the minimum count
24            # occurring in both arrays (element-wise minimum)
25            total_common = sum(min(count, count_2[element]) for element, count in count_1.items())
26          
27            # Append the total number of common elements to the result list
28            result.append(total_common)
29      
30        # Return the final result list containing the common prefix counts
31        return result
32

1class Solution {
2
3    // Function to find the prefix common element count between two arrays.
4    public int[] findThePrefixCommonArray(int[] A, int[] B) {
5        int n = A.length; // Get the length of the array, assumed to be of same length.
6        int[] ans = new int[n]; // Array to store the count of common elements for each prefix.
7        int[] countA = new int[n + 1]; // Array to count occurrences in A, 1-indexed.
8        int[] countB = new int[n + 1]; // Array to count occurrences in B, 1-indexed.
9
10        // Iterate over the arrays A and B simultaneously.
11        for (int i = 0; i < n; ++i) {
12            // Count the occurrences of each element in both arrays.
13            ++countA[A[i]];
14            ++countB[B[i]];
15
16            // Calculate the number of common elements for each prefix (up to the current i).
17            for (int j = 1; j <= n; ++j) {
18                ans[i] += Math.min(countA[j], countB[j]); // Add the minimum occurrences among both arrays.
19            }
20        }
21        return ans; // Return the array of counts.
22    }
23}
24

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find the prefix common element count array
8    vector<int> findThePrefixCommonArray(vector<int>& arrA, vector<int>& arrB) {
9        int size = arrA.size();
10        vector<int> prefixCommonCount(size); // Result array to hold prefix common counts
11        vector<int> countArrA(size + 1, 0); // Count array for elements in arrA
12        vector<int> countArrB(size + 1, 0); // Count array for elements in arrB
13      
14        // Iterate through each element in the input arrays
15        for (int i = 0; i < size; ++i) {
16            // Increment the count of the current elements in arrA and arrB
17            ++countArrA[arrA[i]];
18            ++countArrB[arrB[i]];
19          
20            // Calculate the common elements count for the prefix ending at index i
21            for (int j = 1; j <= size; ++j) {
22                // Add the minimum occurrence count of each element seen so far in both arrays
23                prefixCommonCount[i] += min(countArrA[j], countArrB[j]);
24            }
25        }
26        // Return the resulting prefix common count array
27        return prefixCommonCount;
28    }
29};
30

1function findThePrefixCommonArray(A: number[], B: number[]): number[] {
2    // Determine the length of the arrays
3    const length = A.length;
4
5    // Initialize count arrays for both A and B with zeroes
6    const countA: number[] = new Array(length + 1).fill(0);
7    const countB: number[] = new Array(length + 1).fill(0);
8
9    // Initialize the array to store the result
10    const result: number[] = new Array(length).fill(0);
11
12    // Iterate through elements of arrays A and B
13    for (let i = 0; i < length; ++i) {
14        // Increment the count for the current elements in A and B
15        ++countA[A[i]];
16        ++countB[B[i]];
17
18        // Check for common elements upto the current index
19        for (let j = 1; j <= length; ++j) {
20            // Add the minimum occurrence of the current element in A and B to result
21            result[i] += Math.min(countA[j], countB[j]);
22        }
23    }
24    // Return the result array containing counts of common elements for each prefix
25    return result;
26}
27

Time and Space Complexity

Time Complexity

The given code has a time complexity of O(n^2). This is due to the nested loop implicitly created by the sum function, which sums over items of cnt1 inside the for a, b in zip(A, B) loop. Since the sum operation has to visit each element in the cnt1 dictionary for every element of arrays A and B, the total number of operations will be proportional to n^2, where n is the length of arrays A and B.

Space Complexity

The space complexity is O(n) because we use two Counter objects cnt1 and cnt2 that, in the worst-case scenario, may contain as many elements as there are in arrays A and B, which leads to a linear relationship with n. Additionally, an answer array ans of size n is maintained.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know