Arrays & Hashing · LC #349
Intersection of Two Arrays
Find all unique elements present in both of two integer arrays. Teaches set-intersection via hash-set membership testing and contrasts with the sorted two-pointer variant.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given two integer arrays `nums1` and `nums2`, return an array of their **intersection**, each element appearing only once in the result.
Sample I/O
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4]
Time: O(n+m) · Space: O(n)
Intuition
How to Think About It
Intuition
Converting the smaller array to a set gives O(1) per lookup. We then scan the second array and collect elements that hit the set - a classic "needle in haystack" pattern. Using a result set automatically deduplicates.
Core Concept
Build set1 from nums1. Iterate nums2; for each element in set1, add it to a result set (ensuring uniqueness). Convert result set to array. Python reduces this to a single `&` operator. Time: O(n + m). Space: O(min(n, m)) for the smaller set.
When to use
Finding common elements across two unsorted collections. Database-style INNER JOIN semantics on a small dimension. Building "seen in both" filters in streaming pipelines.
When NOT to use
When you need duplicate-preserving intersection (LC #350, Intersection of Two Arrays II) - use a frequency map. When both arrays are already sorted - two-pointer in O(1) space is optimal.
Key Insights
What to Know Cold
- Build the set from the smaller array to minimise memory.
- Use a result set (not list) when iterating the second array to avoid adding duplicates.
- Python's `set & set` is the most concise form but hides the underlying O(n+m) work.
- For sorted arrays the two-pointer approach achieves O(1) extra space - worth knowing as a follow-up.
- If arrays are streaming/too large for memory, use Bloom filters or an external merge-sort intersection.
1 example
Worked Examples
Set Intersection
nums1 = [1,2,2,1], nums2 = [2,2]. Find unique common elements.
Convert nums1 to set {1,2}. Scan nums2: both 2s are in the set. Result set de-dupes to {2}. Return [2].
nums1, nums2 = [1,2,2,1], [2,2] print(list(set(nums1) & set(nums2))) # [2]
Set intersection is a fundamental building block: used in search engines (document overlap), recommendation systems (shared item sets), and database query planning.