Problem overview
The method intersection receives two vector<int> references, first and second. It returns a new vector with the numbers that appear in both. Each number appears once in the result however often it occurs in the inputs, and the result is sorted in ascending order. Each input holds between 1 and 1000 numbers, from -1000 to 1000.
For first = [1, 2, 2, 1] and second = [2, 2] the answer is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4] the answer is [4, 9]: both numbers occur in both vectors, 8 occurs only in second, and 5 only in first.
The lesson asks for O(n + m) time, plus the time to sort the shared numbers, where n and m are the two lengths.
Approach: remember one vector, then scan the other
The brute-force way checks, for each number in one vector, whether it occurs anywhere in the other. That is O(n * m). A hash table answers the question "have I seen this number?" in constant time on average, so each vector needs to be walked only once.
The plan has three parts:
- Put every number of the shorter vector into an
unordered_mapwith a count of 0. Duplicates collapse into a single key, which gives the uniqueness the result needs. - Walk the longer vector. For each number that is a key, add 1 to its count. Numbers that aren't keys are ignored. Afterwards, a key with a count above 0 appeared in both vectors.
- Collect those keys and sort them. A hash map hands out its entries in no particular order, while the answer must be ascending.
On first = [4, 9, 5] and second = [9, 4, 9, 8, 4], the first vector is the shorter, so the map starts as 4: 0, 9: 0, 5: 0. Walking second gives 9: 2, 4: 2, with 8 skipped and 5 left at 0. The keys with a positive count are 4 and 9, and sorting them gives [4, 9].
Putting the shorter vector into the map keeps the map small. It never holds more than min(n, m) keys.
Step by step
- Copy both inputs into
nums1andnums2withauto. The deduced type isvector<int>, so these are real copies and the next step can reorder them without touching the caller's vectors. - Declare
unordered_map<int, int> d. Keys are numbers from the shorter vector and values are match counts. - Swap if
nums1is longer. Afterswap(nums1, nums2),nums1is the shorter one. - Loop over
nums1withint i. - Set
d[i] = 0. This registers each number once. A repeated number just sets the same key to 0 again. - Loop over
nums2, again withint i. - Skip numbers that aren't keys.
d.find(i) == d.end()means the number isn't in the map, socontinue. - Otherwise add one with
d[i] = d[i] + 1. A key with a count above 0 now records a number found in both vectors. - Declare
vector<int> resultto hold the answer. - Loop over the map with the structured binding
auto& [k, val], which names the key and the value of each entry. - Keep the keys whose
valis above 0 withresult.push_back(k). - Sort
resultand return it. The order of a hash map's entries is unspecified, so the sort is what makes the result ascending.
The solution in C++
class Solution {
public:
vector<int> intersection(vector<int>& first, vector<int>& second) {
auto nums1 = first;
auto nums2 = second;
unordered_map<int, int> d;
if (nums1.size() > nums2.size()) swap(nums1, nums2);
for (int i : nums1) {
d[i] = 0;
}
for (int i : nums2) {
if (d.find(i) == d.end()) continue;
else d[i] = d[i] + 1;
}
vector<int> result;
for (auto& [k, val] : d) {
if (val > 0) result.push_back(k);
}
sort(result.begin(), result.end());
return result;
}
};
C++ details worth a closer look:
autocopies.auto nums1 = first;deducesvector<int>, not a reference, so it makes a copy. Writingauto& nums1 = first;would bind a reference and the laterswapwould exchange the contents of the caller's vectors.swapon vectors is cheap.swap(nums1, nums2)exchanges the internal buffers without copying the elements, so it takes constant time.finddoes not insert.d.find(i)returns an iterator, andd.end()means "not found". Usingd[i]for the test instead would insert every missing number with the value 0 and break the logic that only the shorter vector's numbers are keys.- Assignment through
operator[].d[i] = 0inserts the key if it is missing and overwrites the value if it exists. Since the shorter vector is fully registered before the second loop starts, no count is lost. - Structured bindings.
auto& [k, val](C++17) unpacks each map entry, which is apair<const int, int>. The keykis const because changing a key inside a hash map is not allowed.valis a reference to the stored count. - Result order. The loop over
dvisits entries in an unspecified order, so the finalsortis required for the ascending result. Without it the output could be right on one input and wrong on another.
Complexity
Time: O(n + m) on average, plus the sort. Copying the vectors, filling the map and scanning the longer vector are each linear, and every hash operation takes constant time on average. Collecting the keys visits the map once. Sorting a result of r shared numbers costs O(r log r), which is where the lesson's "plus the time to sort the shared numbers" comes in. Since r is at most min(n, m), the sort never costs more than O(min(n, m) log min(n, m)).
Space: O(n + m). The two copies take O(n + m). The map and the result each hold at most min(n, m) numbers.
Edge cases and common mistakes
- No common numbers.
[1, 2]and[3, 4]leave every count at 0, so the result is an empty vector. - Duplicates.
[1, 2, 2, 1]and[2, 2]give[2], not[2, 2]. The map has one key per distinct number, and the result is built from keys. - Inputs of different lengths. The swap makes the first loop always cover the shorter vector. The answer is the same either way, but the map stays small.
- Negative numbers. Values from -1000 to 1000 work as map keys, and
sortorders negative numbers before positive ones, so[-1, 0]and[0, -1]give[-1, 0]. - Skipping the sort. An
unordered_mapdoesn't remember insertion order or sort its keys, so the result must be sorted explicitly. - Using
d[i]to test membership. It inserts missing keys. Usefind(orcount) to look without changing the map.
Testing
first = [1, 2, 2, 1],second = [2, 2]gives[2].first = [4, 9, 5],second = [9, 4, 9, 8, 4]gives[4, 9].first = [1, 2],second = [3, 4]gives[].first = [-1, 0, 7],second = [7, 0, -1, -1]gives[-1, 0, 7].
