2657. Find the Prefix Common Array of Two Arrays
Difficulty: Medium
Topics: Array
, Hash Table
, Bit Manipulation
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
.
A sequence of n
integers is called a permutation if it contains all integers from 1
to n
exactly once.
Example 1:
- Input: A = [1,3,2,4], B = [3,1,2,4]
- Output: [0,2,3,4]
-
Explanation: At i = 0: no number is common, so C[0] = 0.
- At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
- At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
- At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.
Example 2:
- Input: A = [2,3,1], B = [3,1,2]
- Output: [0,1,3]
-
Explanation: At i = 0: no number is common, so C[0] = 0.
- At i = 1: only 3 is common in A and B, so C[1] = 1.
- At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
Constraints:
1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
It is guaranteed that A and B are both a permutation of n integers.
Hint:
- Consider keeping a frequency array that stores the count of occurrences of each number till index i.
- If a number occurred two times, it means it occurred in both A and B since they’re both permutations so add one to the answer.
Solution:
We can iterate over the two arrays A and B while keeping track of the numbers that have occurred at or before the current index in both arrays. Since both arrays are permutations of the same set of numbers, we can utilize two hash sets (or arrays) to store which numbers have appeared at or before the current index in both arrays. For each index, we can count the common numbers that have appeared in both arrays up to that point.
Solution Approach:
- Use two arrays to keep track of the occurrences of numbers in both
A
andB
up to indexi
. - For each index
i
, check if bothA[i]
andB[i]
have been seen before. If so, increment the common count. - Use a frequency array to track the presence of numbers from
1
ton
in both arrays.
Let's implement this solution in PHP: 2657. Find the Prefix Common Array of Two Arrays
<?php
/**
* @param Integer[] $A
* @param Integer[] $B
* @return Integer[]
*/
function findThePrefixCommonArray($A, $B) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 2, 3, 4]
$A = [2, 3, 1];
$B = [3, 1, 2];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 1, 3]
?>
Explanation:
-
Frequency Arrays: We maintain two frequency arrays,
freqA
andfreqB
, where each index represents a number in the permutation.- When we encounter a number in
A[i]
orB[i]
, we increase the corresponding value in the frequency array.
- When we encounter a number in
-
Common Count: After updating the frequency arrays for both
A[i]
andB[i]
, we check for each number if it has appeared in both arrays up to indexi
. If so, we increase thecommonCount
. -
Result: The common count is stored in the
result
array for each index.
Example Walkthrough:
For the input:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
- At
i = 0
: No common numbers yet →C[0] = 0
- At
i = 1
: Numbers1
and3
are common →C[1] = 2
- At
i = 2
: Numbers1
,2
, and3
are common →C[2] = 3
- At
i = 3
: Numbers1
,2
,3
, and4
are common →C[3] = 4
Output: [0, 2, 3, 4]
Time Complexity:
-
O(n2): For each index
i
, we are checking every element from1
ton
to see if it's common, making this solution quadratic in time complexity. This is acceptable given the constraint n ≤ 50.
This should work within the given constraints effectively.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)