Jobs

Interviews

Discussions

Intersection of Multiple Arrays

Easy

Asked by:

7 views

Topics:

ArraysBit Manipulation

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.

Example 1:

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation: 
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: 
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints:

1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
All the values of nums[i] are unique.

Try coding it in LeetCode

Intersection of Multiple Arrays

Easy

Asked by:

7 views

Topics:

ArraysBit Manipulation

Example 1:

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation: 
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: 
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints:

1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
All the values of nums[i] are unique.

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 is the expected data type of the numbers within the arrays (e.g., integers, floating-point numbers)? What are the possible value ranges for these numbers?
Can any of the input arrays be null or empty? If so, what should the output be?
Are the numbers within each array guaranteed to be unique, or can there be duplicates? Should the output contain duplicate intersection values if they exist in multiple input arrays?
Is there a specific order in which the intersection numbers should be returned (e.g., ascending, descending, order of appearance in the first array)?
If there is no intersection between the arrays, what should the function return (e.g., an empty array, null)?

Brute Force Solution

Approach

The brute force method for finding common elements in multiple lists involves checking every possible number to see if it appears in all of them. We essentially go through each number in one list and compare it to every number in all other lists. If a number is present in all lists, we've found a common element.

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

Take the first list.
For each number in the first list, go to the second list.
Check if that number exists in the second list. If it doesn't, move on to the next number in the first list.
If the number is found in the second list, move to the third list and check if the number exists there.
Keep doing this for all the lists. If the number appears in every list, then it's a common element.
Remember to keep track of all the common elements found.
Once you have checked all the numbers in the first list, you will have found all the common numbers that appear in all of the lists.

Code Implementation

def intersection_of_multiple_arrays(arrays):
    if not arrays:
        return []

    first_array = arrays[0]
    common_elements = []

    for number_in_first_array in first_array:
        is_common = True

        # Iterate through the rest of the arrays
        for other_array in arrays[1:]:

            #Check if number exists in the other array
            if number_in_first_array not in other_array:
                is_common = False
                break

        # If the number is in all the arrays, add it to the result
        if is_common:
            common_elements.append(number_in_first_array)

    return common_elements

Big(O) Analysis

Time Complexity

O(n*m*k) – Let n be the length of the first list, m be the average length of the remaining lists, and k be the number of lists. We iterate through each of the n elements in the first list. For each element in the first list, we search for it in the next list, which takes O(m) time. This search process is repeated for all remaining k-1 lists. Therefore, the overall time complexity is O(n * m * (k-1)), which simplifies to O(n*m*k) as k-1 approximates k when scaling.

Space Complexity

O(1) – The provided brute force algorithm iterates through the lists without using any significant auxiliary data structures. It primarily relies on comparisons and doesn't create any temporary lists, hash maps, or other data structures that scale with the input size, N (where N is the total number of elements across all lists). The algorithm might use a few variables to track the current element being checked and potentially a flag to indicate if the element is present in all lists, but these require constant space. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The best way to find common elements across multiple lists is to count how often each element appears. Then, identify elements that show up in every single list. This avoids comparing every single element in every list with all the others.

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

First, go through each list and count how many times each element shows up across all of them.
Next, check which elements have a count that matches the total number of lists.
Finally, gather all the elements that appear in every single list. That result is the intersection.

Code Implementation

def find_intersection_of_arrays(list_of_lists):
    element_counts = {}

    # Count occurrences to avoid direct comparisons.
    for current_list in list_of_lists:
        for element in current_list:
            if element in element_counts:
                element_counts[element] += 1
            else:
                element_counts[element] = 1

    intersection_result = []

    # Identify elements present in ALL lists.
    for element, count in element_counts.items():
        if count == len(list_of_lists):
            intersection_result.append(element)

    return intersection_result

Big(O) Analysis

Time Complexity

O(n*m) – The first step iterates through each of the m arrays, and within each array iterates up to n times where n is the average length of the arrays. The purpose is to count the frequency of each element. The second step iterates through the frequency count which can have up to n*m keys, and the third step iterates through these to find which ones have a count equal to m, which is constant time per element. Therefore, the dominant cost is the first loop, which scales with O(n*m), where n is the average length of the input arrays and m is the number of arrays.

Space Complexity

O(N) – The primary auxiliary space usage comes from the hash map (or dictionary) used to count element occurrences across all lists, as described in the plain English explanation. In the worst-case scenario, all elements across all input lists are unique. Thus, the hash map may need to store a count for each unique element. Therefore, where N is the total number of elements across all input lists, the space used by the hash map would grow linearly with N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input list of arrays	Return an empty list indicating no intersection exists.
One or more input arrays are null or empty	Treat empty arrays as contributing nothing to the intersection, so the result is empty.
Arrays with extremely large sizes, approaching memory limits	Use a memory-efficient approach like counting occurrences rather than repeatedly creating new sets.
Arrays containing duplicate elements	The intersection should only contain unique elements, even if duplicates exist in the input arrays.
Arrays with very different lengths (e.g., one array has 1 element, others have millions)	Iterate through the smallest array to minimize the number of checks required.
Arrays contain very large numbers potentially leading to overflow if summing for comparison	Avoid summing; compare elements directly or use a hash table to avoid arithmetic operations.
No common elements exist between any of the arrays	The solution should return an empty list in this case, indicating no intersection.
Arrays contain negative numbers, zeros, and positive numbers	The solution must correctly handle all number ranges, without type-specific errors.

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 is the expected data type of the numbers within the arrays (e.g., integers, floating-point numbers)? What are the possible value ranges for these numbers?
Can any of the input arrays be null or empty? If so, what should the output be?
Are the numbers within each array guaranteed to be unique, or can there be duplicates? Should the output contain duplicate intersection values if they exist in multiple input arrays?
Is there a specific order in which the intersection numbers should be returned (e.g., ascending, descending, order of appearance in the first array)?
If there is no intersection between the arrays, what should the function return (e.g., an empty array, null)?

Brute Force Solution

Approach

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

Take the first list.
For each number in the first list, go to the second list.
Check if that number exists in the second list. If it doesn't, move on to the next number in the first list.
If the number is found in the second list, move to the third list and check if the number exists there.
Keep doing this for all the lists. If the number appears in every list, then it's a common element.
Remember to keep track of all the common elements found.
Once you have checked all the numbers in the first list, you will have found all the common numbers that appear in all of the lists.

Code Implementation

def intersection_of_multiple_arrays(arrays):
    if not arrays:
        return []

    first_array = arrays[0]
    common_elements = []

    for number_in_first_array in first_array:
        is_common = True

        # Iterate through the rest of the arrays
        for other_array in arrays[1:]:

            #Check if number exists in the other array
            if number_in_first_array not in other_array:
                is_common = False
                break

        # If the number is in all the arrays, add it to the result
        if is_common:
            common_elements.append(number_in_first_array)

    return common_elements

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, go through each list and count how many times each element shows up across all of them.
Next, check which elements have a count that matches the total number of lists.
Finally, gather all the elements that appear in every single list. That result is the intersection.

Code Implementation

def find_intersection_of_arrays(list_of_lists):
    element_counts = {}

    # Count occurrences to avoid direct comparisons.
    for current_list in list_of_lists:
        for element in current_list:
            if element in element_counts:
                element_counts[element] += 1
            else:
                element_counts[element] = 1

    intersection_result = []

    # Identify elements present in ALL lists.
    for element, count in element_counts.items():
        if count == len(list_of_lists):
            intersection_result.append(element)

    return intersection_result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input list of arrays	Return an empty list indicating no intersection exists.
One or more input arrays are null or empty	Treat empty arrays as contributing nothing to the intersection, so the result is empty.
Arrays with extremely large sizes, approaching memory limits	Use a memory-efficient approach like counting occurrences rather than repeatedly creating new sets.
Arrays containing duplicate elements	The intersection should only contain unique elements, even if duplicates exist in the input arrays.
Arrays with very different lengths (e.g., one array has 1 element, others have millions)	Iterate through the smallest array to minimize the number of checks required.
Arrays contain very large numbers potentially leading to overflow if summing for comparison	Avoid summing; compare elements directly or use a hash table to avoid arithmetic operations.
No common elements exist between any of the arrays	The solution should return an empty list in this case, indicating no intersection.
Arrays contain negative numbers, zeros, and positive numbers	The solution must correctly handle all number ranges, without type-specific errors.