Intersection of Two Arrays easy
Description
Given two integer arrays nums1 and nums2, return their intersection as an array. Each element in the result must be unique, and you may return the result in any order.
Examples
> Case 1:
nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2]
> Case 2:
nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [9, 4] (or [4, 9])Constraints
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Approach 1: Two sets — the canonical answer
Convert one array to a set, then iterate the other and collect elements that are in the set.
Time O(n + m), space O(n) for the smaller-array set.
Approach 2: Sort + two pointers
If you can’t use extra hash-map memory (or the arrays are already sorted), use two pointers.
Time O(n log n + m log m), space depends on the sort (O(1) for in-place quicksort).
Approach comparison
| Approach | Time | Space | When to pick |
|---|---|---|---|
| Two sets | O(n + m) | O(min(n, m)) | Default — simpler and faster |
| Sort + two pointers | O(n log n + m log m) | O(1) extra | When arrays are already sorted, or you need to avoid hash memory |
For the given constraints (n, m ≤ 1000), both work in microseconds. In a real interview, mention both — and explain why two sets is the better default.
The “convert one collection to a set, scan the other” pattern is one of the most common hash-map plays. Same shape solves: Intersection of Two Arrays II (with duplicates), Common Words in 3 Strings, Find Duplicates in Two Sorted Streams. The hash set gives you O(1) “is this in the other collection?”
Variant: Intersection of Two Arrays II (keep duplicates)
If duplicates count ([1,2,2,1] ∩ [2,2] = [2,2] instead of [2]), use a counter instead of a set:
from collections import Counter
def intersect(nums1, nums2):
c1 = Counter(nums1)
result = []
for x in nums2:
if c1[x] > 0:
result.append(x)
c1[x] -= 1
return resultThe counter tracks remaining capacity per value. Each match decrements; when capacity hits zero, no more matches for that value.
Analysis
- Time: O(n + m) with the two-set approach.
- Space: O(min(n, m)) — we only need to store the smaller array’s set.