Thomas Ngo

Software Engineer

3 minute read

Problem Statement

problem

Intuition

The problem requires us to find the prefix common array of two arrays. My first thought was to use sets to keep track of the elements we have seen so far in both arrays. By comparing the elements at each index, we can determine how many elements are common in the prefix.

Approach

  1. Initialize two sets, setA and setB, to keep track of elements seen in arrays A and B respectively.
  2. Initialize a result list res with zeros, and a counter count to keep track of the number of common elements.
  3. Iterate through the arrays using enumerate and zip to get the index and elements from both arrays.
  4. Add the current elements from B to setA and from A to setB.
  5. Compare the current elements from both arrays:
    • If the elements are different, check if the element from A is in setA and if the element from B is in setB, and update the counter accordingly.
    • If the elements are the same and present in either set, increment the counter.
  6. Update the result list with the current count.
  7. Return the result list.

Complexity

  • Time complexity:

    The time complexity is \(O(n)\) because we iterate through the arrays once.

  • Space complexity: The space complexity is \(O(n)\) due to the additional space used by the sets and the result list.

Code

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        setA = set()
        setB = set()
        res = [0] * len(A)
        count = 0
        for i, [x, y] in enumerate(zip(A, B)):
            setA.add(y)
            setB.add(x)
            if x != y:
                if x in setA:
                    count += 1
                if y in setB:
                    count += 1
            elif x == y and (x in setA or y in setB):
                count += 1
            res[i] = count
        return res##

Editorial

Brute Force

class Solution:
    def findThePrefixCommonArray(self, A: list, B: list) -> list:
        n = len(A)
        prefix_common_array = [0] * n

        # Loop through each index to calculate common elements for each prefix
        for current_index in range(n):
            common_count = 0

            # Compare elements in A and B within the range of current prefix
            for a_index in range(current_index + 1):
                for b_index in range(current_index + 1):

                    # Check if elements match, and count if they do
                    if A[a_index] == B[b_index]:
                        common_count += 1
                        break  # Prevent counting duplicates

            # Store the count of common elements for the current prefix
            prefix_common_array[current_index] = common_count

        # Return the final list with counts of common elements in each prefix
        return prefix_common_array
  • time: O(n^3)
  • space O(n)

Approach 2: Hash Set

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        prefix_common_array = [0] * n

        # Initialize sets to store elements from A and B
        elements_in_A, elements_in_B = set(), set()

        # Iterate through the elements of both arrays
        for current_index in range(n):

            # Add current elements from A and B to respective sets
            elements_in_A.add(A[current_index])
            elements_in_B.add(B[current_index])

            common_count = 0

            # Count common elements between the sets
            for element in elements_in_A:
                if element in elements_in_B:
                    common_count += 1

            # Store the count of common elements for the current prefix
            prefix_common_array[current_index] = common_count

        # Return the final array with counts of common elements in each prefix
        return prefix_common_array
  • time: O(n^2)
  • space O(n)

Approach 3: Single Pass with Frequency Array

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        n = len(A)
        prefix_common_array = [0 for _ in range(n)]
        frequency = [0 for _ in range(n + 1)]
        common_count = 0

        # Iterate through the elements of both arrays
        for current_index in range(n):

            # Increment frequency of current elements in A and B
            # Check if the element in A has appeared before (common in prefix)
            frequency[A[current_index]] += 1
            if frequency[A[current_index]] == 2:
                common_count += 1

            # Check if the element in B has appeared before (common in prefix)
            frequency[B[current_index]] += 1
            if frequency[B[current_index]] == 2:
                common_count += 1

            # Store the count of common elements for the current prefix
            prefix_common_array[current_index] = common_count

        # Return the final array with counts of common elements in each prefix
        return prefix_common_array
  • time: O(n)
  • space O(n)

You may also enjoy