2657. Find the Prefix Common Array of Two Arrays

MediumArrayHash Table
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. Iterate Until the End: Repeat steps 3 to 5 until the algorithm reaches the end of the arrays A and B.

  7. 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.

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

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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:

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

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

  1. Initialization: We create empty ans, cnt1, and cnt2 lists/dictionaries.

  2. Simultaneous Traversal: We begin iterating over both A and B using the zip() function.

  3. 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}.

  4. 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.

  5. Appending to ans:

    • Now, ans = [0].

  6. 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}.

  7. 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.

  8. Appending to ans:

    • Now, ans = [0, 1].

  9. 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}.

  10. 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.

  11. Appending to ans:

    • Finally, ans = [0, 1, 3].

  12. 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
Not Sure What to Study? Take the 2-min Quiz：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

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.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫