Problem overview
The function removeDuplicates(nums: IntArray): IntArray receives an array of integers and must return a new array that contains each distinct value once. The order of the result may be anything, but the lesson's solution keeps each value at its first position. For [2, 3, 1, 1, 4, 3, -2, 1] the result is [2, 3, 1, 4, -2].
The statement allows O(n^2) time and O(n) extra space. Extra space is expected here, because the answer is a new array.
Approach: keep a list of values already seen
Walk through nums from left to right, and for each value ask a single question: has this value appeared before? If not, it goes into a separate collection of unique values. If yes, it is skipped. At the end, the collection holds each distinct value exactly once.
The easy way to answer the question is to look through the unique values collected so far. A list can do that with contains. The search checks the elements one by one, so a single lookup costs time proportional to the size of the list, and doing it once per element of nums gives O(n^2) in total. The statement accepts this. A hash set answers the same question in constant time on average and brings the whole solution down to O(n), but this lesson stays with the list.
A list is the right container because the result grows as values are found, and an IntArray has a fixed size that can't be known in advance.
Take [2, 3, 1, 1, 4, 3, -2, 1]. The list grows like this: 2 is new, 3 is new, 1 is new, the second 1 is already there, 4 is new, the second 3 is already there, -2 is new, and the last 1 is already there. The final list is [2, 3, 1, 4, -2].
Step by step
- Create the list. Declare
val uniqueValues = mutableListOf<Int>(). It starts empty and will hold each value the first time it is met. The wordvalonly fixes which list the name refers to. The contents of a mutable list can still change. - Loop over the values. The indices aren't needed, so write
for (value in nums). Each pass gives you the next element directly. - Add only new values. Test
!uniqueValues.contains(value), and when it is true, calluniqueValues.add(value). The!reverses the answer, so the body runs only for values not yet stored. - Convert and return. The function must return an
IntArray, so finish withuniqueValues.toIntArray(), which copies the list into a primitive array.
The solution in Kotlin
class Solution {
fun removeDuplicates(nums: IntArray): IntArray {
val uniqueValues = mutableListOf<Int>()
for (value in nums) {
if (!uniqueValues.contains(value)) {
uniqueValues.add(value)
}
}
return uniqueValues.toIntArray()
}
}
The Kotlin details worth knowing:
MutableListversusList.listOfcreates a read-only list that has noaddfunction. Withval u = listOf<Int>(), the callu.add(1)fails withunresolved reference 'add'.mutableListOfcreates a list you can change.valand mutation. Avalcan't be pointed at another list ('val' cannot be reassigned), but adding elements to the list it points to is fine.IntArrayversusMutableList<Int>. They are different types, and neither converts to the other automatically. ReturninguniqueValuesdirectly would not compile.toIntArray()makes the conversion.- Boxing. A
MutableList<Int>stores boxedIntegerobjects, while anIntArraystores plain ints. Converting at the end is a copy, which addsO(n)work but doesn't change the overall complexity. containsandin.uniqueValues.contains(value)can also be writtenvalue in uniqueValues. Both compare the elements withequals, which for numbers means equal values.- The input is not modified. The function builds a separate list and a separate result, and the caller's array keeps its duplicates.
Complexity
Time: O(n^2). The loop runs n times. Each pass calls contains, which scans a list that can hold up to n values. The worst case is an input where all values differ: the lists seen by successive calls have lengths 0, 1, 2, and so on, and the total is about n^2 / 2 comparisons. The final toIntArray() adds O(n).
Space: O(n). The list holds up to n values when there are no duplicates, and the returned array has the same size.
Edge cases and common mistakes
- Empty array. The loop never runs and the function returns an empty array.
- All values equal.
[5, 5, 5]gives[5]. - No duplicates.
[1, 2, 3]comes back unchanged, as a new array. - Negative numbers and zero. They are ordinary values: the example contains
-2, and it is kept once. - Forgetting the
!. Without it, only values already in the list get added, and since the list starts empty, the result is always empty. - Returning the list. The declared return type is
IntArray, so aMutableList<Int>is a type error. - Using
listOf. A read-only list can't grow. UsemutableListOf. - Removing from the array being scanned. Arrays have a fixed size, so the approach of deleting duplicates in place doesn't fit; build a new collection instead.
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives[2, 3, 1, 4, -2].[5, 5, 5]gives[5].[1, 2, 3]gives[1, 2, 3].[]gives[].