Start learning free

LESSON 202 OF 348 · SORTING

Remove Duplicates From Array in Kotlin: O(n log n), In Place

Practice O(n log n) Read the full explanation

Given an array of integers, remove the duplicates in-place such that each unique element appears only once.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

The resulting array can be in any order.

Example:

Input: [2, 3, 1, 1, 4, 3, -2, 1]
Output: [2, 3, 1, 4, -2]

Note:

Your algorithm should run in O(n log n) time and use O(1) extra space.


Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another. Also, let's remove the O(1) extra space constraint for now to make the problem easier. Let's use an extra array uniqueVals and push the unique values from nums there.

Then, we can traverse the sorted array nums from left to right using an index i. We should push nums[i] into uniqueVals only if that value has not been seen before. How can we check this?

nums[i] has never been seen before if nums[i] != nums[i - 1].

It's time to solve the question with the original constriant. We will still traverse sorted nums but each time we find a new unique element, we will overwrite an element of nums with this value, starting from the left:
  • The first unique value will be stored in nums[0]
  • The second unique value will be stored in nums[1]
  • ...
How can we achieve this?

We will use an index variable p, initially equal to 0, to keep track of where we should place the next unique value we find.

We will traverse nums and check if nums[i] != nums[i - 1]. If so, we will set nums[p] to nums[i] and increment p. What should we return when we finish the traversal?

We should return the subarray nums[0...p].

STEP 1 OF 7
    Ctrl + Enter to check

    KOTLIN · SORTING

    Remove Duplicates From Array in Kotlin, explained

    Problem overview

    removeDuplicates takes an IntArray named nums and returns an IntArray in which every value appears once. The order of the result doesn't matter, and the work should happen inside nums with O(1) extra memory, apart from the returned array.

    For [2, 3, 1, 1, 4, 3, -2, 1], the unique values are 2, 3, 1, 4 and -2. This solution returns them in sorted order, [-2, 1, 2, 3, 4], which the problem allows.

    Approach

    An easy version uses a set or a second list: walk the array and keep a value only if it is new. That needs extra memory proportional to the number of unique values.

    Sorting avoids it. Once the array is sorted, duplicates form runs of equal neighbours, and a value is new exactly when it differs from the element before it. We then use the front of the same array as the output. A write position p marks where the last unique value was stored. Every time a new value appears, we advance p and copy the value there. Since p never gets ahead of the element being read, we never overwrite a value we still need.

    For the sorted array [-2, 1, 1, 1, 2, 3, 3, 4]: p starts at 0 (holding -2). At index 1 the value 1 is new, so p becomes 1 and nums[1] = 1. Indices 2 and 3 are repeats and are skipped. Index 4 holds 2, which is new, so p = 2 and nums[2] = 2, and so on. At the end p = 4, and the first five elements, [-2, 1, 2, 3, 4], are the answer.

    Step by step

    1. Handle the empty array. If nums.isEmpty(), return it. Everything after this assumes a first element exists, and copyOfRange(0, p + 1) on an empty array would throw an IndexOutOfBoundsException.
    2. Sort in place with nums.sort(), so equal values become neighbours.
    3. Create p with var, starting at 0. The first element is always kept, and it already sits at index 0.
    4. Loop over 1 until nums.size. Index 0 is already in place, so the scan starts at the second element.
    5. Check for a new value. If nums[i] != nums[i - 1], the value is met for the first time.
    6. Record it. Increment p first (p++ on its own line), then assign nums[p] = nums[i]. The order matters: p points at the last stored value, so the next free slot is p + 1.
    7. Return the unique prefix. The unique values occupy indices 0 to p, which is p + 1 values. copyOfRange(0, p + 1) copies them into a new array, since the end index is exclusive.

    The solution in Kotlin

    class Solution {

    fun removeDuplicates(nums: IntArray): IntArray {
        if (nums.isEmpty()) {
            return nums
        }
        nums.sort()
        var p = 0
        for (i in 1 until nums.size) {
            if (nums[i] != nums[i - 1]) {
                p++
                nums[p] = nums[i]
            }
        }
        return nums.copyOfRange(0, p + 1)
    }
}

    Kotlin details worth knowing:

    • A Kotlin array can't shrink. That is why the function returns a new, shorter array with copyOfRange instead of deleting from nums.
    • After the loop, the elements past index p in nums still hold leftover values. For [2, 3, 1, 1, 4, 3], nums ends as [1, 2, 3, 4, 3, 4]. Only the returned copy is clean, so use that, not nums.
    • Comparing with nums[i - 1] stays correct even though the loop writes into the array. A write during iteration i lands at index p, which is never greater than i, and when p equals i it writes the value that is already there. So the next iteration still sees the sorted original value at index i.
    • Function parameters can't be reassigned, but the array they refer to can be modified. That is why in-place changes to nums compile.

    Complexity

    • Time: O(n log n) for the sort, plus one O(n) pass and an O(n) copy.
    • Space: O(1) beyond the returned array: the deduplication itself reuses nums.

    The extra-memory version that collects values in a second list has the same running time but uses O(n) space in the worst case, when all values are different. The sorted, in-place version trades a little extra thinking about indices for that saved memory.

    Edge cases and common mistakes

    • Empty input. Covered by the first check. Without it, even the unconditional nums.sort() is harmless, but the final copyOfRange(0, 1) is not.
    • One element. The loop doesn't run, p is 0, and the result is a one-element copy.
    • All values equal. [5, 5, 5] gives [5].
    • Returning nums itself. It still has the leftover tail, so it is longer than the answer.
    • Returning p elements. copyOfRange(0, p) drops the last unique value, because p is an index, not a count.
    • Forgetting the sort. Duplicates that aren't adjacent, such as the two 3s in [3, 1, 3], would both survive.
    • Assigning before incrementing. Writing nums[p] = nums[i] before p++ overwrites the last stored unique value.

    Testing

    • [2, 3, 1, 1, 4, 3, -2, 1] returns [-2, 1, 2, 3, 4].
    • [7] returns [7].
    • [] returns an empty array.
    • [3, 1, 3] returns [1, 3].

    The first call returns the unique values in sorted order, not in their original order. The problem accepts any order, so that is fine, but it is worth knowing if you compare the output by eye with the example in the statement, which lists them differently.

    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free