Problem overview
The function removeDuplicates receives an IntArray called nums and returns a new IntArray that holds each value of nums exactly once. The result may be in any order. For [2, 3, 1, 1, 4, 3, -2, 1] the answer holds 2, 3, 1, 4, -2, in some order.
The statement asks for O(n) time and O(n) extra space.
Approach: let a set do the work
A set stores each value at most once, and adding a value that is already in it changes nothing. So if you add every element of the array to a HashSet, what remains afterwards is exactly the list of distinct values. Adding is constant time on average, so the loop is linear.
The simpler approaches cost more. Comparing every pair is O(n²). Sorting first and then dropping neighbours that repeat is O(n log n). The hash set avoids both, at the price of the extra O(n) space the statement allows.
The set doesn't remember the order in which values went in, which is fine, because the statement accepts any order.
Here is the idea on [2, 3, 1, 1, 4, 3, -2, 1]. After 2, 3 and the first 1, the set holds three values. The second 1 is already there, so nothing changes. 4 and -2 are new and go in. The second 3 and the third 1 change nothing. The set ends with five values, and those are the answer.
Step by step
- Create the set.
uniqueValuesis avalholding a new emptyHashSet<Int>. The variable never changes; the set's contents do. - Add every element. A
forloop names each elementvalueand callsuniqueValues.add(value). Nocontainscheck is needed:addsimply does nothing, and returnsfalse, when the value is already present. - Convert and return. The function must return an
IntArray, and the set is not one, sotoIntArray()copies its elements into a new array.
The solution in Kotlin
class Solution {
fun removeDuplicates(nums: IntArray): IntArray {
val uniqueValues = HashSet<Int>()
for (value in nums) {
uniqueValues.add(value)
}
return uniqueValues.toIntArray()
}
}
Details worth knowing:
toIntArray()is defined on collections ofInt, so it works on theHashSet<Int>directly. It produces a new array and leaves the set alone. ASet<Int>is not anIntArray, and Kotlin won't convert one to the other on its own.- The returned array is new, so
numsis not modified. - The elements come out in the order the set iterates them. For small integers that often looks sorted, but nothing guarantees it, so don't depend on it.
- The loop calls
addand ignores itsBooleanresult. That is fine in Kotlin: a function's result may be discarded.
Complexity
Time is O(n): the loop makes n constant-time add calls on average, and toIntArray() copies at most n elements. Space is O(n) for the set and the result array, in the worst case where all values are different.
Edge cases and common mistakes
- Empty input. The set stays empty and the function returns an empty array.
- All values equal.
[5, 5, 5]gives an array with the single element5. - Expecting the original order. A
HashSetdoesn't preserve it. If order mattered, you would need aLinkedHashSet(linkedSetOf), but this lesson doesn't require it. - Returning the set. The declared return type is
IntArray, so returning the set doesn't compile. Convert it first. - Using
toSet()ordistinct()without understanding them. They solve the same problem in one call, but the lesson builds the set by hand so you see the mechanism.
Testing
[2, 3, 1, 1, 4, 3, -2, 1]returns the five values2, 3, 1, 4, -2, in any order.[]returns[].[5, 5, 5]returns[5].