Problem overview
The method removeDuplicates receives an array of integers and returns a new array that contains each distinct value once. The result may be in any order. For [2, 3, 1, 1, 4, 3, -2, 1] a correct answer holds 2, 3, 1, 4 and -2, for example [2, 3, 1, 4, -2].
The statement asks for O(n) time and O(n) extra space.
Approach: let a set do the work
Because the order of the result is free, there is nothing to preserve, and a hash set is a perfect fit. A set keeps at most one copy of each value, and inserting a value that is already present does nothing. So the plan is to insert every element and turn the set back into an array. Each insertion is constant time on average, which gives O(n) for the whole pass.
Other approaches exist. Sorting first and skipping neighbours that are equal costs O(n log n). Checking each new value against the result array with contains scans that array every time and costs O(n²). The set avoids both.
Step by step
- Create the set.
uniqueValuesis an emptySet<Int>declared withvar. - Insert every element. A
for value in numsloop callsuniqueValues.insert(value). No check is needed first: inserting an existing value leaves the set unchanged. - Convert and return.
Array(uniqueValues)builds an[Int]from the set's elements in one expression.
The solution in Swift
class Solution {
func removeDuplicates(_ nums: [Int]) -> [Int] {
var uniqueValues = Set<Int>()
for value in nums {
uniqueValues.insert(value)
}
return Array(uniqueValues)
}
}
Swift details worth a closer look:
- The order is not stable. A
Sethas no defined order, and Swift can order the same elements differently on each run of a program. For the example, the result holds exactly 2, 3, 1, 4 and -2, but their order may change from run to run. That is fine here because the statement allows any order. When you need a predictable order, useuniqueValues.sorted(), which also returns an array; for the example it gives[-2, 1, 2, 3, 4]. - Shortcut.
Array(Set(nums))does the whole job in one line. The loop spells out what theSetinitializer does for you. - Keeping the original order. If a task needs the first occurrence of each value in its original position, keep a set of values seen and append to the result only when
insertreports a new value. - Value types. The input array is never modified. The method builds a separate set and a separate array, so the caller's array stays as it was.
Complexity
Time: O(n). There are n insertions at constant average cost, plus one pass to copy the set into an array.
Space: O(n). The set and the result array each hold up to n values.
Edge cases and common mistakes
- Empty input. The set stays empty and the method returns
[]. - No duplicates. The result has the same values as the input, possibly in a different order.
- Comparing with an expected array. Comparing the result directly with
[2, 3, 1, 4, -2]can fail even when the answer is right, because the order is not fixed. Sort both sides, or compare them as sets. - Using the array as the "seen" collection.
result.contains(value)works but turns the algorithm intoO(n²).
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives the values -2, 1, 2, 3, 4 once each (sorted:[-2, 1, 2, 3, 4]).[]gives[].[5, 5, 5]gives[5].
