Find the Prefix Common Array of Two Arrays

Medium

Asked by:

29 views

Topics:

Arrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values within arrays A and B? Can they be negative, zero, or are there any upper limits?
What is the maximum possible length of the arrays A and B?
Are there any guarantees about the uniqueness of elements within each array? Can an element appear multiple times within array A or array B?
If A and B have no common elements at any prefix, should I return an array filled with zeros, or is there another specific value I should use to represent zero common elements?
Can the input arrays A and B ever be null or empty?

Brute Force Solution

Approach

The basic idea is to go through the arrays piece by piece, comparing them at each step. We build a new array to store the count of common numbers we've seen so far for each comparison.

Here's how the algorithm would work step-by-step:

Start by looking at only the first number in each of the two input arrays.
Check if those two numbers are the same. If they are, the common number count for that first position is one, otherwise it's zero.
Now, look at the first two numbers in each input array.
For each position (up to the second number), check if the numbers at that position are the same in both input arrays, or if the number from the first array is present anywhere in the second array up to this position and vice versa. Keep a running tally of common numbers we find.
Repeat this process, each time considering one more number from each input array.
For each increase, create new running tally of how many numbers in the part we are currently looking at are also present in the other input arrays section.
The end result is an array showing the number of common elements seen up to each position in the input arrays.

Code Implementation

def find_prefix_common_array(array_one, array_two):    length_of_arrays = len(array_one)
    prefix_common_array = []

    for i in range(length_of_arrays):
        common_count = 0

        # Iterate through prefixes of both arrays
        for j in range(i + 1):

            # Check if element is present in both prefixes
            if array_one[j] in array_two[:i + 1] and array_two[j] in array_one[:i + 1]:
                common_count += 1

        prefix_common_array.append(common_count)

    return prefix_common_array

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates 'n' times, extending the prefix considered in both input arrays. In each iteration, it compares each element of the prefix of the first array with all the elements of the prefix of the second array to count common elements. This nested comparison leads to approximately n * n operations. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The algorithm creates a new array to store the count of common numbers for each prefix. Since the algorithm iterates N times (where N is the length of the input arrays), the resulting array, representing prefix common counts, will have a length of N. Additionally, in each step, it implicitly keeps track of seen elements. We need to remember the elements from both arrays up to the current index, and since we're checking for presence within those prefixes, the storage required would increase linearly with N. Thus, the auxiliary space scales linearly with the input size N, leading to a space complexity of O(N).

Optimal Solution

Approach

To efficiently find the common elements in the prefixes of two collections, we'll use a way to remember which items we've seen. This lets us quickly check for matches without re-examining everything repeatedly, leading to a much faster process.

Here's how the algorithm would work step-by-step:

First, create a way to keep track of which items from the first collection we've encountered so far.
Now, go through the collections together, element by element, from the beginning.
For each element in the second collection, check if we've seen it before in the first collection using our memory.
If we have seen it before, it's a common element at that point in the prefix. Count it.
Also, add the current element from the first collection to our memory, so we remember it for future comparisons.
Repeat this process for each pair of elements in the two collections.
The count we've been keeping tells us how many common elements each prefix has, so keep track of the count at each step.

Code Implementation

def find_prefix_common_array(array_a, array_b):
    prefix_common_count_array = []
    seen_elements = set()
    common_count = 0

    for index in range(len(array_a)): 
        #Iterate through each element in both arrays.
        element_b = array_b[index]
        element_a = array_a[index]

        if element_b in seen_elements:
            # Found common element, increment
            common_count += 1

        seen_elements.add(element_a)
        # Keep track of the number of common elements seen so far.
        prefix_common_count_array.append(common_count)

    return prefix_common_count_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input arrays A and B once, element by element, up to the length n of the arrays. Inside the loop, it performs a constant-time lookup in a set to check for the presence of an element and a constant-time insertion into the set. Since the loop dominates the execution time and the operations within the loop are constant time, the overall time complexity is directly proportional to the input size n, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a data structure (described as "a way to keep track of which items from the first collection we've encountered so far") to store elements from the first array. In the worst case, all N elements of the first array are distinct, and this data structure (likely a set or hash map) will store all of them. Therefore, the auxiliary space used grows linearly with the input size N. The space complexity is thus O(N).

Edge Cases

Case	How to Handle
Null or Empty A or B arrays	Return an empty list or throw an IllegalArgumentException as there's nothing to compare.
A and B arrays have different lengths	Throw an IllegalArgumentException or return an empty list, as the problem states they have the same length.
Arrays A and B are of length 1	Check if A[0] equals B[0] and return [1] or [0] accordingly.
Arrays A and B contain large integers causing potential integer overflow	The prefix common array elements will not be affected by integer overflow in A and B themselves, only the count itself might overflow if the array length is sufficiently large and mostly common elements occur.
Arrays A and B contain duplicate values	The hash set or map based solution implicitly handles duplicates correctly as only the presence or absence of a value is important.
Arrays A and B are identical	The prefix common array C will be [1, 2, 3, ..., n], where n is the length of A (or B).
Arrays A and B have no common elements	The prefix common array C will be all zeros: [0, 0, 0, ..., 0].
Arrays A and B contain negative numbers	Hash set or map solution handles negative numbers without any modification.

Null or Empty A or B arrays

How to Handle:

Return an empty list or throw an IllegalArgumentException as there's nothing to compare.

A and B arrays have different lengths

How to Handle:

Throw an IllegalArgumentException or return an empty list, as the problem states they have the same length.

Arrays A and B are of length 1

How to Handle:

Check if A[0] equals B[0] and return [1] or [0] accordingly.

Arrays A and B contain large integers causing potential integer overflow

How to Handle:

The prefix common array elements will not be affected by integer overflow in A and B themselves, only the count itself might overflow if the array length is sufficiently large and mostly common elements occur.

Arrays A and B contain duplicate values

How to Handle:

The hash set or map based solution implicitly handles duplicates correctly as only the presence or absence of a value is important.

Arrays A and B are identical

How to Handle:

The prefix common array C will be [1, 2, 3, ..., n], where n is the length of A (or B).

Arrays A and B have no common elements

How to Handle:

The prefix common array C will be all zeros: [0, 0, 0, ..., 0].

Arrays A and B contain negative numbers

How to Handle:

Hash set or map solution handles negative numbers without any modification.