#349
Intersection of Two Arrays
Easy HashSet
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the distinct values present in both arrays.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: distinct values present in both arrays.
Why this works: put one array in a set; remove a value when found so it's reported once.
Example: [1, 2, 2, 1] and [2, 2]
set {1, 2}2 found → remove → [2]; next 2 not in set
✦Hints open one at a time
Put one array into a set.
Walk the other array; when a value is in the set, record it and remove it so it's recorded once.
↗Approach
Set from nums1, then for each value of nums2 that is removed successfully from the set, add it to the result.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for (int x : nums1) set.add(x);
List<Integer> res = new ArrayList<>();
for (int x : nums2) {
if (set.remove(x)) res.add(x); // remove so it's added once
}
int[] out = new int[res.size()];
for (int i = 0; i < out.length; i++) out[i] = res.get(i);
return out;
}
}!Common mistake
Returning duplicates when a common value repeats in nums2.
Complexity
- Time: O(n + m).
- Space: O(n).
Topic: Hashing
🎬 Episodes 37–39: video coming soon