Start learning free

LESSON 226 OF 415 · SORTING

Remove Duplicates From Array in Swift: Sort and Overwrite

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 uniqueValues and add the unique values from nums there.

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

The element at index i has never been seen before if it is different from the element at index i - 1.

It's time to solve the question with the original constraint. 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 at index 0 of nums
  • The second unique value will be stored at index 1
  • ...
How can we achieve this?

We will use an index variable p, initially equal to 0, to keep track of the index where the last unique value was placed.

We will traverse nums and check if the element at index i is different from the element at index i - 1. If so, we will increment p and then copy the element at index i to index p. What should we return when we finish the traversal?

We should return the first p + 1 elements of nums.

STEP 1 OF 7
    Ctrl + Enter to check

    SWIFT · SORTING

    Remove Duplicates From Array in Swift, explained

    Problem overview

    The method removeDuplicates receives an array of integers and returns an array in which every value appears exactly once. The order of the result doesn't matter.

    For [2, 3, 1, 1, 4, 3, -2, 1] the distinct values are -2, 1, 2, 3 and 4. This solution returns them in ascending order, [-2, 1, 2, 3, 4], which is a valid answer because any order is accepted.

    Approach: sort, then compact in place

    Once the array is sorted, equal values are neighbours, so a value is new exactly when it differs from the element before it. The simplest way to use that is to push each new value into a second array. The idea of this lesson is to avoid the second array and overwrite the front of the sorted one instead.

    Keep an index p that marks where the last distinct value was stored. The first element is always kept, so p starts at 0. Walk through the rest of the array with i. Whenever nums[i] differs from nums[i - 1], it is a new value: move p one step forward and copy nums[i] into nums[p]. Since p never gets ahead of i, the write never overwrites a value that hasn't been read yet. At the end, positions 0 through p hold the distinct values in order.

    Trace [1, 1, 2, 2, 3]. At i = 1 the value equals its neighbour. At i = 2 the value 2 is new, so p becomes 1 and nums[1] is set to 2. At i = 3 nothing happens. At i = 4, 3 is new, p becomes 2 and nums[2] is set to 3. The array is now [1, 2, 3, 2, 3], and the first p + 1 = 3 elements are the answer.

    Why the overwrite is safe

    At the start of each iteration, p is at most i - 1: it begins at 0 when i is 1, and it grows by at most 1 per iteration, just as i does. So a write to nums[p + 1] lands at index i or below. When it lands at i, the value is copied onto itself. When it lands lower, it overwrites an element that has already been read, and the elements at i and after are untouched. The neighbour comparison therefore always sees the original sorted values.

    Other approaches exist. A Set would remove duplicates in O(n) time without sorting, but it doesn't keep any order and needs extra memory. This lesson practises the sorted, in-place idea.

    Step by step

    1. Return early for an empty array. The rest of the function assumes a first element. With none, the loop range 1..<nums.count would run from 1 to 0, and the final slice nums[0...p] would be out of bounds. Swift crashes on both.
    2. Sort in place. Parameters are constants in Swift, so the function first makes a mutable copy named nums, then calls sort() on it.
    3. Declare p as 0. It holds the position of the last distinct value stored.
    4. Loop i over 1..<nums.count. The first element is already in place.
    5. Compare with the previous element: nums[i] != nums[i - 1].
    6. Store a new value. Increment p first, then assign nums[p] = nums[i].
    7. Return the first p + 1 elements as an array.

    The solution in Swift

    class Solution {

    func removeDuplicates(_ nums: [Int]) -> [Int] {
        var nums = nums
        if nums.isEmpty {
            return nums
        }
        nums.sort()
        var p = 0
        for i in 1..<nums.count {
            if nums[i] != nums[i - 1] {
                p += 1
                nums[p] = nums[i]
            }
        }
        return Array(nums[0...p])
    }
}

    The Swift details worth knowing:

    • Shadowing the parameter. var nums = nums declares a new variable with the same name as the parameter. From that line on, nums means the copy. Arrays are values in Swift, so sorting the copy never changes the caller's array.
    • Closed range for the slice. nums[0...p] includes index p, which holds the last distinct value. That is why it has p + 1 elements. Using 0..<p would drop the last value.
    • ArraySlice to Array. A range subscript returns an ArraySlice<Int>. The function returns [Int], so the slice is wrapped in Array(...).
    • No ++. Swift has no increment operator, so the code writes p += 1.
    • The empty case. isEmpty is the idiomatic check. It reads better than nums.count == 0.

    Complexity

    Time: O(n log n). Sorting takes O(n log n) and the compaction loop is a single pass of O(n).

    Space: O(n) in Swift. The compaction itself needs only the index p, so it works in place on the sorted array. In Swift, though, the function copies its parameter into var nums, and the returned array is a second, smaller array, so total memory use is proportional to n. A function that took the array as inout would avoid the first copy.

    Edge cases and common mistakes

    • Empty array. The early return gives []. Without it the program crashes.
    • One element. [7] skips the loop (the range 1..<1 is empty), p stays 0, and the result is [7].
    • All equal. [5, 5] never moves p, so the result is [5].
    • Skipping the sort. Duplicates may be far apart, and the neighbour comparison would let them through.
    • Moving p after the assignment. Writing nums[p] = nums[i] before p += 1 overwrites the last distinct value instead of adding a new one.
    • Returning nums itself. After compaction the tail of the array still holds leftover values. In the trace above, [1, 2, 3, 2, 3] is not the answer.

    Testing

    • [2, 3, 1, 1, 4, 3, -2, 1] gives [-2, 1, 2, 3, 4].
    • [] gives [].
    • [7] gives [7].
    • [5, 5] gives [5].
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free