Intersection of Two Arrays
Return the unique elements common to both arrays — hash set lookup.
2 min read
hash-set arrays
Problem#
Given two integer arrays nums1 and nums2, return their intersection — each element appears once in the result, in any order.
Examples#
nums1 = [1,2,2,1], nums2 = [2,2]→[2].nums1 = [4,9,5], nums2 = [9,4,9,8,4]→[9,4].
Constraints#
1 <= nums1.length, nums2.length <= 1000,0 <= nums[i] <= 1000.
Hints#
Hint
Put one array in a set; scan the other and collect hits.
Approach#
Build unordered_set from nums1. Walk nums2; on hit, append to result and erase from the set to dedupe automatically.
Solution#
class Solution {public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> set1(nums1.begin(), nums1.end()); vector<int> ans; for (int v : nums2) { auto it = set1.find(v); if (it != set1.end()) { ans.push_back(v); set1.erase(it); } } return ans; }};func intersection(nums1 []int, nums2 []int) []int { set1 := make(map[int]bool, len(nums1)) for _, v := range nums1 { set1[v] = true } ans := []int{} for _, v := range nums2 { if set1[v] { ans = append(ans, v) delete(set1, v) } } return ans}from typing import List
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: set1 = set(nums1) ans: List[int] = [] for v in nums2: if v in set1: ans.append(v) set1.remove(v) return ansfunction intersection(nums1, nums2) { const set1 = new Set(nums1); const ans = []; for (const v of nums2) { if (set1.has(v)) { ans.push(v); set1.delete(v); } } return ans;}class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<>(); for (int v : nums1) set1.add(v); List<Integer> ans = new ArrayList<>(); for (int v : nums2) { if (set1.remove(v)) ans.add(v); } int[] out = new int[ans.size()]; for (int i = 0; i < ans.size(); i++) out[i] = ans.get(i); return out; }}function intersection(nums1: number[], nums2: number[]): number[] { const set1: Set<number> = new Set(nums1); const ans: number[] = []; for (const v of nums2) { if (set1.has(v)) { ans.push(v); set1.delete(v); } } return ans;}Editorial#
Erasing on hit is what enforces uniqueness in the result without a second pass or output set. Memory grows with the smaller of the two inputs if you choose to set-ify the smaller side.
Complexity#
- Time: O(N + M).
- Space: O(N).
Concept revision#
Related#