Problem overview
The function removeRepeats gets a list of integers nums and returns a new list in which each value appears once. It keeps the first copy of each value and drops the later ones, so the values stay in the order they first appear.
For [3, 1, 3, 2, 1] the answer is [3, 1, 2]: the second 3 and the second 1 are repeats. For [6, 6, 6, 6] it is [6], and for [4, 9, 2], where nothing repeats, the list comes back unchanged. The list has at least one number, and each number is between -1,000,000,000 and 1,000,000,000, which fits in a Kotlin Int (32 bits, up to about 2.1 billion).
Approach
Read the numbers from left to right and remember which ones you have already met. A number that is new goes into the result. A number that was seen before is skipped. A HashSet is ideal for the remembering, because checking whether it holds a value is fast; searching the result list for each number would be slower.
Reading in order is what keeps the first copy: the first time a value shows up it is not yet in the set, so it is kept, and every later copy is found in the set and skipped. The set itself has no order, so the result list is what carries the order.
Step by step
- Create the set of seen values:
hashSetOf<Int>(), in avalnamedseen. The type in angle brackets tells Kotlin what the empty set will hold. - Create the result: an empty
mutableListOf<Int>(), in avalnamedresult. - Loop over
numswith the variablenum. - Inside, check
!seen.contains(num). The!turns the answer around, so the condition is true whennumis not in the set yet. - Inside that
if, addnumtoresult. - Also add
numtoseen, so a later copy is recognised. - After the loop, return
result.
The solution in Kotlin
class Solution {
fun removeRepeats(nums: List<Int>): List<Int> {
val seen = hashSetOf<Int>()
val result = mutableListOf<Int>()
for (num in nums) {
if (!seen.contains(num)) {
result.add(num)
seen.add(num)
}
}
return result
}
}
The function returns a List<Int>, and the MutableList it builds can be returned as one. The tests print the values separated by spaces, so the three examples print:
3 1 2
6
4 9 2
Another way
Kotlin's library has distinct(), which does the same job: listOf(3, 1, 3, 2, 1).distinct() gives [3, 1, 2]. It is worth knowing, but the loop shows how it works. Building a set from the list is not the same thing: listOf(3, 1, 3, 2, 1).toHashSet() printed [1, 2, 3] in a test run, with the order not following the list, and a set is not a list anyway.
Complexity
Each number is looked at once, and the set check and the add are fast, so the time grows in step with the length of nums. The set and the result together use extra space of about the same size.
Edge cases and common mistakes
- Returning the set. It would lose the order and has the wrong type.
- Forgetting
seen.add(num). Nothing would ever be marked as seen, and the result would equal the input. - Returning inside the loop. Only the first number would come back.
- Keeping the last copy instead of the first. That happens if you scan from the right, or overwrite earlier results. Read left to right.
