How do you solve Intersection of Multiple Arrays on LeetCode?

Intersection of Multiple Arrays (LeetCode #2248) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashMap allows efficient counting of occurrences across multiple arrays.

What is the brute force solution for Intersection of Multiple Arrays?

The brute force approach for Intersection of Multiple Arrays is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each integer in every array to see if it appears in all arrays. This is straightforward but inefficient because it involves a lot of repeated checks. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Intersection of Multiple Arrays?

Intersection of Multiple Arrays uses the following concepts: Array, Hash Table, Sorting, Counting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Intersection of Multiple Arrays?

Always clarify the constraints and requirements of the problem before diving into coding. Think about edge cases, such as empty arrays or arrays with no common elements. Explain your thought process clearly while coding; this helps the interviewer understand your approach.

What are common mistakes when solving Intersection of Multiple Arrays?

Not considering the case where arrays have no common elements, leading to incorrect results. Forgetting to handle duplicates within the same array, even though the problem states they are distinct.

#2248

Intersection of Multiple Arrays

Easy

ArrayHash TableSortingCountingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a HashMap to count occurrences of each integer across all arrays. This is efficient because it allows us to determine which integers appear in every array with a single pass through the data.

⚙️

Algorithm

4 steps

1Step 1: Create a HashMap to count occurrences of each integer.
2Step 2: Iterate through each array and update the count for each integer in the HashMap.
3Step 3: Collect integers that have a count equal to the number of arrays.
4Step 4: Sort the result list before returning it.

solution.py9 lines

1from collections import defaultdict
2
3def intersection(nums):
4    count = defaultdict(int)
5    for arr in nums:
6        for num in set(arr):
7            count[num] += 1
8    result = [num for num, cnt in count.items() if cnt == len(nums)]
9    return sorted(result)

ℹ

Complexity note: The time complexity is O(n) because we only pass through the data a couple of times (once to count and once to filter). The space complexity is O(n) due to the HashMap storing counts of each integer.

1Using a HashMap allows efficient counting of occurrences across multiple arrays.
2Sorting the result at the end ensures the output is in ascending order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.