LESSON 261 OF 409 · HASH TABLE

Find Duplicates in C++: O(n) with unordered_map

Given an array of integers, return a new array containing only the duplicates.

The resulting array's values can be stored in any order.

Example:

Input: [2, 3, 1, 1, 4, 3, 2, 1]
Output: [2, 1, 3]

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 7

Guided

Ctrl + Enter to check

C++ · HASH TABLE

Find Duplicates in C++, explained

Problem overview

The method findDuplicates receives a vector<int>& nums and returns a new vector<int> with the values that appear more than once. Each duplicated value is listed one time, however many copies exist, and the result may be in any order.

For [2, 3, 1, 1, 4, 3, 2, 1] the values 1, 2 and 3 repeat (1 three times, 2 and 3 twice) and 4 appears once. The answer contains 1, 2 and 3. The statement shows [2, 1, 3]; the solution below produces [1, 3, 2], which is the same set in a different order and is accepted.

The statement asks for O(n) time and O(n) extra space.

Approach: count as you go

The obvious way to test a value is to compare it with every other element, which costs O(n²). Sorting first would bring equal values together and give O(n log n). To reach O(n), remember what has been seen. A hash table answers "have I seen this value before?" in constant time on average.

In C++ that table is unordered_map<int, int>. The key is a number from nums and the value is how many times it has appeared so far. One pass over the vector is enough: add one to the count of each value as you read it.

The one subtle point is when to add a value to the result. Doing it whenever the count is above 1 would add a value that appears four times three times. Doing it when the count becomes exactly 2 adds each duplicate once, at the moment its second copy turns up. Third and later copies take the count to 3, 4 and so on, and are ignored.

Another way is to sort a copy of the vector and compare neighbours: after sorting, equal values sit next to each other, so a duplicate is a value equal to the one before it. That costs O(n log n) time, which is slower than the lesson asks for, and it needs extra care to avoid listing a value that appears three times more than once. The hash table keeps the original order of discovery and runs in one pass.

Step by step

Declare result, a vector<int> that collects each duplicate when it is found.
Declare freq, an unordered_map<int, int> from each number to its count so far.
Loop over nums with a range-based for and an int value. Each element is visited once, in order.
Increment freq[value]. No special case is needed for a number seen for the first time. operator[] inserts a missing key with the value 0, and ++ turns that into 1.
Test freq[value] == 2. This is true exactly once per duplicated value, on its second occurrence.
Add the value to result with push_back inside that if.
Return result after the loop.

The solution in C++

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> result;
        unordered_map<int, int> freq;
        for (int value : nums) {
            freq[value]++;
            if (freq[value] == 2) {
                result.push_back(value);
            }
        }
        return result;
    }
};

Details worth a closer look:

freq[value]++ relies on operator[] inserting. For a missing key, unordered_map::operator[] creates an entry whose int is value-initialized to 0 and returns a reference to it.
The result is in order of second occurrence. That is why the example gives [1, 3, 2]: the second 1 comes at index 3, the second 3 at index 5 and the second 2 at index 6.
int value copies each element. That is fine for int. The vector itself is passed by reference, so the call does not copy it.
The input is not modified. The function only reads nums.

Here is the loop on [2, 3, 1, 1, 4, 3, 2, 1], showing the count after each increment:

value	count after `++`	added to `result`?
2	1	no
3	1	no
1	1	no
1	2	yes, result is `[1]`
4	1	no
3	2	yes, result is `[1, 3]`
2	2	yes, result is `[1, 3, 2]`
1	3	no, already added

Complexity

Time: O(n). The loop runs n times. Each iteration does a couple of hash lookups, which take constant time on average, and one push_back, which is amortized constant. The worst case for a hash table, many keys colliding, is theoretically slower, but it does not happen with ordinary integer data.

Space: O(n). freq holds one entry per distinct value, up to n. result holds at most n / 2 values.

Edge cases and common mistakes

A value that appears three or more times. For [7, 7, 7, 7] the answer is [7], with one entry. A test of freq[value] > 1 would give [7, 7, 7]. The condition must be exactly == 2.
No duplicates. [1, 2, 3] gives [].
Empty or single-element vector. The loop does nothing or runs once, and the result is [].
Negative numbers and zero. They are ordinary keys. [-1, -1, 0, 0] gives [-1, 0].
Comparing the wrong count. Check the count after incrementing. If you test before the increment, the match is on a count of 1.
Expecting a fixed order. The statement allows any order. If a caller needs a sorted result, sort result after the loop.

Testing

[2, 3, 1, 1, 4, 3, 2, 1] gives [1, 3, 2].
[4, 3, 4, 3] gives [4, 3].
[1, 2, 1, 2, 1, 2] gives [1, 2].
[7, 7, 7, 7] gives [7].
[1, 2, 3], [5] and [] all give [].

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free