Start learning free

LESSON 202 OF 338 · SORTING

Remove Duplicates From Array in Go: O(n log n), O(1) Space

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

    GO · SORTING

    Remove Duplicates From Array in Go, explained

    Problem overview

    The function removeDuplicates receives a slice of integers, nums, and must leave each distinct value exactly once. The work has to happen in place: no second slice, only O(1) extra memory. The order of the result doesn't matter.

    For nums = [2, 3, 1, 1, 4, 3, -2, 1], the distinct values are 2, 3, 1, 4 and -2. The function returns a slice holding those five values. This lesson's approach returns them in ascending order, [-2 1 2 3 4], which is one of the allowed orders.

    The required budget is O(n log n) time and O(1) extra space.

    Approach: sort, then compact the unique values to the front

    A map of seen values would make this easy, but it uses O(n) space. Sorting removes the need for it. Once the slice is sorted, equal values are neighbours, so a value is new exactly when it differs from the element before it.

    First imagine building a second slice uniqueVals and appending each new value to it. The in-place version replaces that slice with the front of nums itself. A write position p marks where the last distinct value was stored. Every time the scan meets a new value, p moves one step and the value is copied there. The write position never overtakes the read position i, so nothing is overwritten before it has been read.

    On the sorted example [-2, 1, 1, 1, 2, 3, 3, 4]:

    • Index 0 (-2) stays where it is, and p is 0.
    • Index 1 holds 1, which differs from -2. p becomes 1, and nums[1] = 1.
    • Indices 2 and 3 hold 1 again, so nothing happens.
    • Index 4 holds 2: p becomes 2, and nums[2] = 2.
    • Index 5 holds 3: p becomes 3, and nums[3] = 3.
    • Index 6 holds 3 again, so nothing happens.
    • Index 7 holds 4: p becomes 4, and nums[4] = 4.

    The first p + 1 = 5 positions now hold -2 1 2 3 4. The slice behind them still contains leftovers, 3 3 4, which the result must not include.

    Step by step

    1. Handle the empty slice first. The rest of the function treats the first element as always kept, and returns nums[:p+1] at the end. With an empty slice that would ask for one element, and a slice expression can't go beyond the capacity, so the program would panic. Returning nums right away avoids this.
    2. Sort in place with sort.Ints, which returns nothing.
    3. Declare p := 0. It is the index of the last distinct value placed so far. The first element is already in place.
    4. Loop with i from 1 while i < len(nums), since the element at index 0 needs no check.
    5. Compare with the previous element using nums[i] != nums[i-1].
    6. On a new value, advance and copy. In Go, p++ is a statement and can't sit inside an index expression, so it goes on its own line before the assignment nums[p] = nums[i].
    7. Return the first p + 1 elements with nums[:p+1]. The count is one more than the index.

    The solution in Go

    func removeDuplicates(nums []int) []int {
    if len(nums) == 0 {
        return nums
    }
    sort.Ints(nums)
    p := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            p++
            nums[p] = nums[i]
        }
    }
    return nums[:p+1]
}

    Go details to notice:

    • The result is a view of the same array. nums[:p+1] has length 5 here, but its capacity is still 8, and the caller's own nums still has length 8 and now reads [-2 1 2 3 4 3 3 4]. Go can't shorten a slice from inside a function that receives it by value, which is why the function returns the new slice, and why the caller must use the return value.
    • A nil slice has length 0, so the guard also returns it unchanged.

    Complexity

    Time: O(n log n). The sort costs O(n log n), and the compaction pass is O(n).

    Space: O(1) extra. The function only keeps p and i, and the sort works in place. The input is modified.

    Edge cases and common mistakes

    • Empty or nil input. The guard returns it as it is. Without the guard, []int{} panics with "slice bounds out of range [:1] with capacity 0".
    • All values equal. [7, 7, 7] never enters the if, so p stays 0 and the result is [7].
    • Already unique values. Every comparison succeeds, p ends at n - 1, and each element is copied onto itself. The result has the same length as the input.
    • Returning nums[:p]. This drops the last distinct value. The index p is inclusive, so the length is p + 1.
    • Using the original nums as the answer. The caller's slice still has the original length, with leftover values after the unique ones. Use the returned slice.
    • Forgetting to sort. Without sorting, equal values can be far apart, and the neighbour comparison no longer detects them.

    Try these in the editor above: the example should return [-2 1 2 3 4], [7, 7, 7] should return [7], and an empty slice should return an empty slice.

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