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 <= 501 <= A[i], B[i] <= nIt is guaranteed that A and B are both a permutation of n integers.This approach involves two sets to track elements of A and B as you traverse them. For each index i, you will check how many elements have been seen in both sets. This allows us to efficiently count common elements at each index.
The solution uses two arrays 'seenA' and 'seenB' to keep track of which numbers from 1 to n have been encountered in arrays A and B respectively. For each element in the arrays, it updates the 'seenA' and 'seenB' arrays and then checks if the element has been seen in both. This allows counting how many numbers have been seen in both arrays up to index i.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), since it iterates through the arrays once. Space Complexity: O(n), due to the arrays used for tracking seen elements.
This approach utilizes a single integer array of length n+1 to track occurrences. As you iterate, you update this array for presence in A and B. The count of elements present in both arrays is updated based on the state of this tracking array.
This solution employs a single integer array 'occurrence' to maintain a count of numbers observed from both arrays. For each number from A and B, it increments the respective index in 'occurrence'. If that index's value becomes 2, it indicates that the number has appeared in both arrays.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n). Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Using Two Sets to Track Common Elements | Time Complexity: O(n), since it iterates through the arrays once. Space Complexity: O(n), due to the arrays used for tracking seen elements. |
| Using a Single Array to Track Presence | Time Complexity: O(n). Space Complexity: O(n). |
Find the Prefix Common Array of Two Arrays | Leetcode 2657 • Techdose • 3,130 views views
Watch 9 more video solutions →Practice Find the Prefix Common Array of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode