Intersection of Two Arrays
The key idea
Membership testing is the whole problem. Put one array's values into a hash set so each lookup is O(1), then keep the values of the other array that are present. The result must be distinct, so collect into a set too.
Problem
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
The intersection is the set of values that appear in both nums1 and nums2. Because each result value is counted at most once, the answer never contains duplicates even when an input array does.
Constraints
- 1 <= nums1.length, nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 1000
Examples
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]
Complexity
Time: O(n + m) Space: O(n + m)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM