2657. Find the Prefix Common Array of Two Arrays
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
, andcnt2
. Here,ans
will store the final response, being the "prefix common array".cnt1
andcnt2
are counters in the form of dictionaries (from thecollections
module in Python) that will keep track of the frequency of each number inA
andB
, respectively. -
Simultaneous Traversal: Using the
zip()
function to simultaneously iterate over bothA
andB
. Thezip()
function pairs the items ofA
andB
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
fromA
andb
fromB
, the algorithm updatescnt1[a]
andcnt2[b]
. This action increments the counts of the elements within our counterscnt1
andcnt2
, 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 indexi
. The minimum is taken betweencnt1[x]
andcnt2[x]
for each numberx
, meaning the number of timesx
has appeared in bothA
andB
up toi
. -
Appending to
ans
: The value calculated in the previous step reflects the total count of common numbers at indexi
in the permutations. This value is appended to theans
list. -
Iterate Until the End: Repeat steps 3 to 5 until the algorithm reaches the end of the arrays
A
andB
. -
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 EvaluatorExample 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
, andcnt2
lists/dictionaries. -
Simultaneous Traversal: We begin iterating over both
A
andB
using thezip()
function. -
Count Incrementation for index 0:
- We start with the first elements in
A
andB
, which are1
and2
. - We increment
cnt1[1]
andcnt2[2]
. - Now,
cnt1 = {1: 1}
andcnt2 = {2: 1}
.
- We start with the first elements in
-
Calculating Intersection:
- We determine the minimum count for each number that has appeared.
- So far,
1
has not appeared inB
and2
has not appeared inA
, thus the common count is 0. - We append
0
toans
.
-
Appending to
ans
:- Now,
ans = [0]
.
- Now,
-
Continue Traversal for index 1:
- Now we take the second elements
3
fromA
and1
fromB
. - We increment
cnt1[3]
andcnt2[1]
. - Now,
cnt1 = {1: 1, 3: 1}
andcnt2 = {2: 1, 1: 1}
.
- Now we take the second elements
-
Calculating Intersection:
- At this point,
1
is the only common number appearing in bothA
andB
. - We append the common count
1
toans
.
- At this point,
-
Appending to
ans
:- Now,
ans = [0, 1]
.
- Now,
-
Final Traversal for index 2:
- For the last element, we have
2
fromA
and3
fromB
. - We update
cnt1[2]
andcnt2[3]
. - Now,
cnt1 = {1: 1, 3: 1, 2: 1}
andcnt2 = {2: 1, 1: 1, 3: 1}
.
- For the last element, we have
-
Calculating Intersection:
- Each number has appeared once in both
A
andB
. - The total common count is the sum of occurrences of each number, which is
3
.
- Each number has appeared once in both
-
Appending to
ans
:- Finally,
ans = [0, 1, 3]
.
- Finally,
-
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 arrayC
that we wanted to construct.
- We have finished iterating through both arrays, and the completed
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.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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
Want a Structured Path to Master System Design Too? Donāt Miss This!