Intersection of Two Arrays

Return the unique elements common to both arrays — hash set lookup.

Easy
Time O(N + M) Space O(N)
LeetCode
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#

Intersection of Two Arrays
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.