Problem overview
The function findDuplicates takes a slice of integers, nums, and returns a new slice with every value that appears more than once, each listed a single time. The order is free. For [2, 3, 1, 1, 4, 3, 2, 1] the duplicates are 2, 3 and 1; the value 4 appears only once and is left out. The statement asks for O(n) time and O(n) extra space.
Approach: count as you go
Counting for every element how many copies exist by rescanning the slice is O(n²). A frequency map gets the counts in one pass: keys are values, entries are how many times each has been seen so far.
A value becomes a duplicate at the moment its count reaches 2. Appending the value at exactly that moment solves two problems at once. The first copy (count 1) is not yet a duplicate, so it is not added. A third, fourth or later copy (count 3, 4, ...) has already been added, so it is not added again. Each duplicate value is therefore recorded once, with no second pass and no need to check whether the result already holds it.
On the example, the second 1 raises its count to 2, so 1 is appended. The second 3 appends 3 and the second 2 appends 2. The third 1 raises its count to 3 and is ignored. The result is [1 3 2], which is in order of each value's second appearance.
Step by step
- Start the result as an empty slice,
result := []int{}. - Create the map
frequencywithmake(map[int]int). - Loop over the values of
numswithfor _, value := range nums. - Increment the count with
frequency[value]++. A first sighting needs no special case, because a missing key reads as 0. - Check for exactly 2. That is the moment the value is first known to be repeated.
- Append it and assign the result of
appendback toresult. - Return
result.
The solution in Go
func findDuplicates(nums []int) []int {
result := []int{}
frequency := make(map[int]int)
for _, value := range nums {
frequency[value]++
if frequency[value] == 2 {
result = append(result, value)
}
}
return result
}
The Go details:
appendreturns the slice. A slice has a length and a capacity over a backing array. When the capacity is exhausted,appendallocates a bigger array, so the possibly new slice must be stored back.[]int{}versusnil. The literal creates an empty, non-nil slice. With no duplicates the function returns[]and notnil.++on a map entry reads (0 if absent), adds one and writes back.++is a statement in Go, not an expression.
Complexity
Time: O(n). One pass, with a map write and a map read per element, each O(1) on average.
Space: O(n). The map has up to n keys, and the result adds at most n / 2 elements.
Edge cases and common mistakes
- Using
>= 2instead of== 2. A value seen three times would be appended twice.[5, 5, 5, 5]must give[5]. - Using
== 1or checking before incrementing. That reports values that appear only once, or reports duplicates one step late. - No duplicates.
[1, 2, 3]gives an empty slice. - Empty input. The loop does not run and the result is empty.
- Order. The result follows the second appearances, not the first.
[1, 1, 2, 2, 1]gives[1 2]. Any order is accepted. - Nil map. A map declared without
makewould panic on the first write.
Testing
[2, 3, 1, 1, 4, 3, 2, 1]gives[1 3 2](any order is valid).[1, 2, 3]gives[].[5, 5, 5, 5]gives[5].[1, 1, 2, 2, 1]gives[1 2].