Problem overview
The function find_duplicates receives a vector of integers and returns a vector of the values that appear more than once, each listed a single time. For [2, 3, 1, 1, 4, 3, 2, 1] the values 1, 2 and 3 repeat, while 4 appears once, so the answer holds 1, 2 and 3. The lesson's version of the function returns them in ascending order: [1, 2, 3].
The lesson asks for O(n) time and O(n) extra space.
Approach: count as you go and report at the second sighting
Comparing every pair of elements finds duplicates in O(n²). A hash map brings it to O(n): keep a count for each value, and update it as the loop passes over the vector.
The key observation is when to record a duplicate. A value becomes a duplicate at the moment its count reaches exactly 2. The first sighting makes the count 1 (not yet a duplicate). The second makes it 2: add the value to the result now. A third sighting makes it 3, and later ones keep growing the count. Testing for equality with 2 instead of "at least 2" means each duplicate is pushed once, however many copies there are.
On [7, 7, 7, 8]: after the first 7 the count is 1, nothing happens. After the second 7 the count is 2, so 7 is pushed. After the third the count is 3, which isn't 2, so nothing is pushed. The 8 stays at 1. The answer is [7].
Tracing the example: the counts grow as 2:1, 3:1, 1:1, then the second 1 brings 1 to 2 and pushes 1. Next 4:1, then the second 3 pushes 3, the second 2 pushes 2, and the third 1 raises its count to 3 without pushing. The vector is [1, 3, 2] at that point, and sort() turns it into [1, 2, 3].
Step by step
- Create the result vector
result, amut Vec<i32>, to hold each duplicate when it is discovered. - Create the map
freq, amut HashMapfrom value to count. The compiler infers the types from the code below. - Loop over
&numswith the pattern&value. The items are&i32references, and the pattern copies each number intovalue. - Increase the count with
*freq.entry(value).or_insert(0) += 1. A new value starts at 0 and then becomes 1. - Check for exactly 2 with
freq[&value] == 2. - Push the value onto
resultinside thatif. - Sort the result with
sort()and return it as the last expression. Sorting puts the duplicates in a predictable order, ascending, which the lesson's tests expect.
The solution in Rust
impl Solution {
fn find_duplicates(nums: Vec<i32>) -> Vec<i32> {
let mut result: Vec<i32> = Vec::new();
let mut freq = HashMap::new();
for &value in &nums {
*freq.entry(value).or_insert(0) += 1;
if freq[&value] == 2 {
result.push(value);
}
}
result.sort();
result
}
}
Rust details:
- The import.
HashMaplives instd::collections. A program of your own needsuse std::collections::HashMap;for the name to resolve. - The entry API.
entry(value).or_insert(0)returns a&mutreference to the count, creating it with 0 when the key is missing. The leading*dereferences it so that+= 1changes the stored count. - Indexing a map.
freq[&value]takes a reference to the key and panics if the key is missing. It is safe here because the line before just created the entry. - Integer defaults. The counts have no annotation, so the compiler picks
i32for them. sort()works in place. It returns nothing, which is whyresultappears alone on the next line.
A variation
The same idea works with two sets: one for values seen once, and one for values already reported. A value that is in the first set and not yet in the second is a new duplicate. The map version is shorter, and it also leaves you with the full count of every value if you want to use it.
Complexity
Time: O(n + d log d), where d is the number of duplicate values. The loop does O(1) average work per element, so it is O(n). The final sort handles only the duplicates. Since d is at most n / 2, the worst case is O(n log n); without the sort, which the lesson's tests require, the algorithm would be O(n).
Space: O(n). The map holds one entry per distinct value, and the result holds up to n / 2 values.
Edge cases and common mistakes
- No duplicates.
[1, 2, 3]returns an empty vector. - Empty vector. The loop doesn't run and the result is empty.
- Many copies of one value.
[5, 5, 5, 5]returns[5]: the count passes through 2 only once. - Testing for "2 or more". Using
>= 2pushes the value again on its third and later sightings, and the result has repeats. - Forgetting the
*in front ofentry(...).or_insert(0). The code then tries to add to a reference and fails to compile. - Printing the map to see the order. A
HashMapiterates in arbitrary order, which is why the answer is built in the loop and sorted, not read from the map.
Testing
[2, 3, 1, 1, 4, 3, 2, 1]gives[1, 2, 3].[5, 5, 5, 5]gives[5].[1, 2, 3]gives[].
