Leetcode 2657: Find the Prefix Common Array of Two Arrays
You are given two integer arrays A and B, each of length n, which are permutations of numbers from 1 to n. You need to find the prefix common array of A and B. The prefix common array is defined as an array C where each C[i] represents the number of integers that appear at or before index i in both A and B.
Problem
Approach
Steps
Complexity
Input: You are given two integer arrays A and B of length n. Both arrays are permutations of integers from 1 to n.
Example: Input: A = [4, 1, 3, 2], B = [2, 1, 4, 3]
Constraints:
• 1 <= A.length == B.length == n <= 50
• 1 <= A[i], B[i] <= n
• A and B are both permutations of integers from 1 to n.
Output: Return the prefix common array, where each element represents the count of common numbers at or before the index i in both arrays A and B.
Example: Output: [0, 1, 2, 3]
Constraints:
• The output should be an array of integers representing the prefix common array.
Goal: The goal is to calculate the prefix common array by checking how many elements from A and B are common up to each index.
Steps:
• Step 1: Iterate through each index of arrays A and B.
• Step 2: Track the common elements up to each index using sets for quick lookup.
• Step 3: Update the prefix common array at each step based on the count of common elements.
Goal: Ensure that the solution works efficiently within the given constraints of n and array sizes.
Steps:
• The arrays A and B are permutations, meaning they contain all integers from 1 to n exactly once.
Assumptions:
• Both arrays A and B contain all integers from 1 to n exactly once.
• Input: Input: A = [4, 1, 3, 2], B = [2, 1, 4, 3]
• Explanation: At index 0: no numbers are common, so C[0] = 0. At index 1: 1 is common, so C[1] = 1. At index 2: 1 and 4 are common, so C[2] = 2. At index 3: 1, 4, 3, and 2 are common, so C[3] = 4.
• Input: Input: A = [5, 2, 4, 1, 3], B = [3, 1, 5, 4, 2]
• Explanation: At index 0: no numbers are common, so C[0] = 0. At index 1: only 2 is common, so C[1] = 1. At index 2: 2 and 5 are common, so C[2] = 2. At index 3: 2, 5, and 4 are common, so C[3] = 3. At index 4: all elements are common, so C[4] = 5.
Approach: The approach involves iterating through both arrays while tracking the common elements up to each index using sets. We will update the prefix common array based on how many elements have been seen in both arrays at each point.
Observations:
• We can use two sets to track the elements we've seen so far in A and B.
• The use of sets allows for efficient checking of common elements.
• We need to efficiently count the common elements at each index and store the results.
Steps:
• Step 1: Initialize two sets, one for tracking elements seen in A and another for elements seen in B.
• Step 2: Iterate through each index of the arrays A and B.
• Step 3: For each index, check if the current element from A is in B and vice versa, updating the count of common elements.
• Step 4: Store the count of common elements at each index in the result array.
Empty Inputs:
• There are no empty inputs as per the problem constraints.
Large Inputs:
• The input size can be up to 50, so the solution should be efficient for arrays of size 50.
Special Values:
• If all elements in A and B are in reverse order, the solution should still work efficiently.
Constraints:
• Ensure that the solution respects the constraint of A and B being valid permutations.
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
set<int> a, b, c;
int n = A.size();
vector<int> ans(n, 0);
for(int i = 0; i < n; i++) {
if(a.count(B[i])) {
c.insert(B[i]);
}
if(b.count(A[i])) {
c.insert(A[i]);
}
if(A[i] == B[i]) {
c.insert(A[i]);
}
a.insert(A[i]);
b.insert(B[i]);
ans[i] = c.size();
}
return ans;
}
1 : Function Definition
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
This defines the function `findThePrefixCommonArray`, which takes two vectors, A and B, as input and returns a vector containing the count of common elements at each prefix index.
2 : Set Initialization
set<int> a, b, c;
Here, three sets are initialized: 'a' and 'b' will store elements from arrays A and B, respectively, while 'c' will store the common elements found in both.
3 : Array Size Calculation
int n = A.size();
This line calculates the size of array A (which is the same as array B) and stores it in the variable 'n'.
4 : Vector Initialization
vector<int> ans(n, 0);
A vector 'ans' of size n is initialized with all elements set to 0. This will store the number of common elements for each prefix.
5 : Looping through Arrays
for(int i = 0; i < n; i++) {
The for loop starts, iterating over each index of arrays A and B to check for common elements.
6 : Set Lookup
if(a.count(B[i])) {
This checks if the current element in array B exists in set 'a' (i.e., if it has already been encountered in array A).
7 : Set Insertion
c.insert(B[i]);
If the element from array B exists in set 'a', it is inserted into set 'c', indicating a common element.
8 : Set Lookup
if(b.count(A[i])) {
This checks if the current element in array A exists in set 'b' (i.e., if it has already been encountered in array B).
9 : Set Insertion
c.insert(A[i]);
If the element from array A exists in set 'b', it is inserted into set 'c', indicating a common element.
10 : Equality Check
if(A[i] == B[i]) {
This checks if the current elements from arrays A and B are equal at the same index.
11 : Set Insertion
c.insert(A[i]);
If the elements at the same index in both arrays are equal, the element is inserted into set 'c' as a common element.
12 : Set Insertion
a.insert(A[i]);
This inserts the current element from array A into set 'a'.
13 : Set Insertion
b.insert(B[i]);
This inserts the current element from array B into set 'b'.
14 : Array Update
ans[i] = c.size();
The current size of set 'c' (which contains the common elements) is stored in the 'ans' vector at the current index.
15 : Return Statement
return ans;
The function returns the 'ans' vector, which contains the count of common elements for each prefix of arrays A and B.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we iterate through the arrays once and perform constant time operations (set insertions and lookups) at each step.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the sets tracking the elements seen in A and B.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus