Jobs

Interviews

Discussions

Intersection of Two Arrays

Easy

Two Sigma

0 views

Topics:

ArraysTwo PointersBinary Search

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

Intersection of Two Arrays

Easy

Two Sigma

0 views

Topics:

ArraysTwo PointersBinary Search

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

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:

Can the input arrays, nums1 and nums2, contain negative numbers or zero?
Are there any constraints on the size of the input arrays nums1 and nums2? Specifically, what is the maximum possible length of each array?
If there are duplicate numbers within a single input array (e.g., nums1 has multiple occurrences of the number 5), how should that affect the intersection? Should only unique intersections be returned?
If there is no intersection between the two arrays, should I return an empty array or null?
Is the order of the numbers in the output array important, or can I return the intersecting numbers in any order?

Brute Force Solution

Approach

The brute force approach to finding common elements in two lists is like comparing each item from one list against every item in the other. If we find a match, we add it to our results. We continue this process until we've checked all possible pairs of items.

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

Take the first list and select its first item.
Compare that item to every single item in the second list.
If you find a match, write down that item as one of the common items.
After comparing the first item of the first list to all items in the second list, move on to the second item of the first list.
Again, compare this item to every single item in the second list.
If you find a match, write down that item as one of the common items (making sure you don't write down the same item twice if it was already there).
Keep doing this for every item in the first list, comparing each one to all the items in the second list.
Once you've gone through every item in the first list, the items you've written down are the common items between the two lists.

Code Implementation

def intersection_of_two_arrays_brute_force(first_array, second_array):
    intersection_result = []

    for first_array_element in first_array:

        # For each element, check against every element in the second array
        for second_array_element in second_array:

            if first_array_element == second_array_element:

                # Ensure we don't add duplicates to the intersection
                if first_array_element not in intersection_result:
                    intersection_result.append(first_array_element)

    return intersection_result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through each element of the first array. For each of these elements, it then iterates through the entirety of the second array to check for equality. If we define 'n' as the length of the first array and 'm' as the length of the second array, this results in n * m comparisons. In the case where both arrays are of similar size, we can approximate 'm' as 'n', giving us n * n operations. Thus, the time complexity is O(n²).

Space Complexity

O(N) – The brute force approach, as described, requires extra space to store the common items found between the two lists. In the worst-case scenario, where all elements in the first list are also present in the second list, we would need to store up to N elements (where N is the number of elements in the first list) in our result list. Therefore, the auxiliary space used grows linearly with the size of the first input list, resulting in O(N) space complexity.

Optimal Solution

Approach

The most efficient way to find common numbers between two lists is to first organize each list individually. Then, we can easily compare them to quickly pinpoint the shared numbers without unnecessary checks.

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

First, take both lists and arrange each one in order from smallest to largest.
Now, imagine you have a pointer at the start of each ordered list.
Compare the numbers at each pointer. If they're the same, that's a number in the intersection, so add it to your result.
If the numbers aren't the same, advance the pointer of the list that has the smaller number.
Keep going until you reach the end of either list. The list of common numbers you collected is your answer.

Code Implementation

def intersection_of_two_arrays(first_array, second_array):
    first_array.sort()
    second_array.sort()

    index_first_array = 0
    index_second_array = 0
    intersection_result = []

    while index_first_array < len(first_array) and index_second_array < len(second_array):
        if first_array[index_first_array] == second_array[index_second_array]:
            # Found a common element, add to result.
            intersection_result.append(first_array[index_first_array])
            index_first_array += 1
            index_second_array += 1
        elif first_array[index_first_array] < second_array[index_second_array]:
            # Advance pointer of the smaller element.
            index_first_array += 1

        else:
            # Advance pointer of the smaller element.
            index_second_array += 1

    return intersection_result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The time complexity is determined by two main operations: sorting and comparing. Sorting each array of size n using an efficient algorithm like merge sort or quicksort takes O(n log n) time. After sorting, we iterate through both arrays using two pointers. In the worst case, we traverse both arrays entirely, taking O(n) time. Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(min(N, M)) – The dominant space usage comes from storing the intersection results. In the worst-case scenario, where 'N' and 'M' represent the sizes of the two input arrays respectively, the intersection could contain at most min(N, M) elements. Therefore, the list to store the intersection requires space proportional to the size of the smaller input array. Other variables used such as the two pointers do not contribute significantly to the space complexity as they use constant space.

Edge Cases

Case	How to Handle
One or both input arrays are null or empty	Return an empty array if either input is null or empty to avoid NullPointerExceptions and undefined behavior.
Arrays contain very large numbers (potential integer overflow)	Use long data types or appropriate data structures if the numbers are likely to exceed the integer limits.
Arrays contain duplicate numbers; ensure only unique intersections are returned	Use a Set to store the intersection to guarantee uniqueness, preventing duplicate entries.
One array is extremely large, while the other is very small	Iterate through the smaller array and check for existence in the larger array (using a HashSet for O(1) lookups in the larger array) to optimize performance.
Arrays contain negative numbers, zeros, and positive numbers	The HashSet or other comparison strategies should correctly handle negative numbers and zeros without additional logic.
No common elements exist between the two arrays	The function should return an empty array, demonstrating that no intersections were found.
Arrays are identical and contain only one element	The function should return an array containing that single element.
Arrays contain extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	The solution should handle these values correctly without causing overflows or unexpected behavior in the comparison or hashing process.

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:

Can the input arrays, nums1 and nums2, contain negative numbers or zero?
Are there any constraints on the size of the input arrays nums1 and nums2? Specifically, what is the maximum possible length of each array?
If there are duplicate numbers within a single input array (e.g., nums1 has multiple occurrences of the number 5), how should that affect the intersection? Should only unique intersections be returned?
If there is no intersection between the two arrays, should I return an empty array or null?
Is the order of the numbers in the output array important, or can I return the intersecting numbers in any order?

Brute Force Solution

Approach

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

Take the first list and select its first item.
Compare that item to every single item in the second list.
If you find a match, write down that item as one of the common items.
After comparing the first item of the first list to all items in the second list, move on to the second item of the first list.
Again, compare this item to every single item in the second list.
If you find a match, write down that item as one of the common items (making sure you don't write down the same item twice if it was already there).
Keep doing this for every item in the first list, comparing each one to all the items in the second list.
Once you've gone through every item in the first list, the items you've written down are the common items between the two lists.

Code Implementation

def intersection_of_two_arrays_brute_force(first_array, second_array):
    intersection_result = []

    for first_array_element in first_array:

        # For each element, check against every element in the second array
        for second_array_element in second_array:

            if first_array_element == second_array_element:

                # Ensure we don't add duplicates to the intersection
                if first_array_element not in intersection_result:
                    intersection_result.append(first_array_element)

    return intersection_result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, take both lists and arrange each one in order from smallest to largest.
Now, imagine you have a pointer at the start of each ordered list.
Compare the numbers at each pointer. If they're the same, that's a number in the intersection, so add it to your result.
If the numbers aren't the same, advance the pointer of the list that has the smaller number.
Keep going until you reach the end of either list. The list of common numbers you collected is your answer.

Code Implementation

def intersection_of_two_arrays(first_array, second_array):
    first_array.sort()
    second_array.sort()

    index_first_array = 0
    index_second_array = 0
    intersection_result = []

    while index_first_array < len(first_array) and index_second_array < len(second_array):
        if first_array[index_first_array] == second_array[index_second_array]:
            # Found a common element, add to result.
            intersection_result.append(first_array[index_first_array])
            index_first_array += 1
            index_second_array += 1
        elif first_array[index_first_array] < second_array[index_second_array]:
            # Advance pointer of the smaller element.
            index_first_array += 1

        else:
            # Advance pointer of the smaller element.
            index_second_array += 1

    return intersection_result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
One or both input arrays are null or empty	Return an empty array if either input is null or empty to avoid NullPointerExceptions and undefined behavior.
Arrays contain very large numbers (potential integer overflow)	Use long data types or appropriate data structures if the numbers are likely to exceed the integer limits.
Arrays contain duplicate numbers; ensure only unique intersections are returned	Use a Set to store the intersection to guarantee uniqueness, preventing duplicate entries.
One array is extremely large, while the other is very small	Iterate through the smaller array and check for existence in the larger array (using a HashSet for O(1) lookups in the larger array) to optimize performance.
Arrays contain negative numbers, zeros, and positive numbers	The HashSet or other comparison strategies should correctly handle negative numbers and zeros without additional logic.
No common elements exist between the two arrays	The function should return an empty array, demonstrating that no intersections were found.
Arrays are identical and contain only one element	The function should return an array containing that single element.
Arrays contain extreme boundary values (Integer.MAX_VALUE, Integer.MIN_VALUE)	The solution should handle these values correctly without causing overflows or unexpected behavior in the comparison or hashing process.