Problem overview
The function removeDuplicates takes a slice of integers, nums, and returns a new slice with each distinct value once. The result may be in any order. For [2, 3, 1, 1, 4, 3, -2, 1] the result holds 2, 3, 1, 4 and -2 in some order. The statement asks for O(n) time and O(n) extra space.
Approach: let a map collapse the duplicates
Comparing every element with every other one is O(n²), and sorting first costs O(n log n). A map does it in one pass. Use the values as keys: storing a key that already exists just overwrites it, so any number of copies of a value end up as a single key. After the pass, the keys are exactly the distinct values, and copying them into a slice gives the answer.
The price is the loss of order. Go deliberately randomizes the order in which a map is traversed, so the result may come out differently from one run to the next. The statement allows any order, so that is acceptable here. If the original order mattered, you would check a set while scanning and append on first sight instead.
On the example, the keys after the first loop are 2, 3, 1, 4 and -2. The second loop copies those five keys into the result.
Step by step
- Create the set
uniqueValuesasmake(map[int]struct{}). The empty struct is the idiomatic value for a set, since it takes no memory. - Fill it. Range over
numsand storestruct{}{}under eachvalue. Repeated values overwrite the same key. - Allocate the result with
make([]int, 0, len(uniqueValues)): length 0 and capacity equal to the number of distinct values, so the appends below never have to reallocate. - Collect the keys. Range over the map with one variable, which yields the keys, and
appendeach toresult. - Return
result.
The solution in Go
func removeDuplicates(nums []int) []int {
uniqueValues := make(map[int]struct{})
for _, value := range nums {
uniqueValues[value] = struct{}{}
}
result := make([]int, 0, len(uniqueValues))
for value := range uniqueValues {
result = append(result, value)
}
return result
}
The Go details:
make([]int, 0, n). The three arguments are the type, the length and the capacity. A slice of length 0 and capacitynis empty but has room fornelements. If you wrotemake([]int, n)instead, it would holdnzeros and the appends would add after them.appendreturns the slice. It may have to allocate a new backing array, so the result is assigned back toresult.- Range with one variable. Over a map it gives the keys. With two it gives key and value, but the values here are empty structs.
- Empty input. For a nil or empty
nums,resultis an empty, non-nil slice of length 0.
Complexity
Time: O(n). The first loop does n map writes and the second loop visits at most n keys, with O(1) average cost for each map operation.
Space: O(n). The map holds up to n keys and the result up to n integers.
Edge cases and common mistakes
- Expecting the original order. The result order is unspecified, so compare with the expected values as a set or sort both before comparing.
- All values equal.
[7, 7, 7]returns[7]. - Empty input. The result is an empty slice.
- Zero capacity mistakes. Using
make([]int, len(uniqueValues))would leave a prefix of zeros in the answer. - Changing the input. The function builds a new slice and leaves
numsuntouched.
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives the five values-2, 1, 2, 3, 4in some order (sorted:[-2 1 2 3 4]).[7, 7, 7]gives[7].[]gives an empty slice.