Skip to content

Latest commit

 

History

History
87 lines (61 loc) · 3.49 KB

040.md

File metadata and controls

87 lines (61 loc) · 3.49 KB

2657. Find the Prefix Common Array of Two Arrays

Difficulty: 🟡 Medium

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:

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.

Solutions

O(n) solution in Python3

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        length, n, count = len(A), max(A), 0
        C, counter = [], [0] * (n+1)
        for a, b in zip(A, B):
            if a == b:
                count += 1
            else:
                counter[a] += 1
                counter[b] += 1
                count += (counter[a] == 2) + (counter[b] == 2)
            C.append(count)
        return C

The given solution calculates the prefix common array, C, by comparing the values in A and B and tracking the counts using a counter array.

The algorithm works as follows:

  1. Initialize length as the length of A (which is equal to B), n as the maximum value in A, count as 0, and C as an empty array.
  2. Initialize a counter array, counter, of size n+1 with all elements set to 0. The counter array will track the counts of the numbers.
  3. Iterate through A and B simultaneously using the zip function:
    • If the values at the current index are equal in A and B, increment the count by 1.
    • Otherwise, increment the count for the values in A and B using the counter array. Update the count by checking if the count for any value in the counter array becomes 2.
    • Append the updated count to the C array.
  4. Return the prefix common array, C.

The algorithm compares the values at each index of A and B and updates the count accordingly, maintaining the prefix common array.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of A (which is equal to B). The algorithm iterates through the arrays A and B once, performing constant-time operations at each iteration.

The space complexity of the algorithm is O(n) as it uses additional space for the C array and the counter array, both of size n.

Summary

The given solution calculates the prefix common array, C, by comparing the values in two permutations, A and B. It has a time complexity of O(n) and a space complexity of O(n), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.