Remove Duplicates from Array in Swift 3.0

Question

I ran the following code through a Leetcode.com challenge and it says the runtime for the test cases is 119ms, which puts it at the back of the pack performance wise.

The goal is to remove duplicates from a sorted array of Ints and return the count of the array without dups.

func removeDuplicates(_ nums: inout [Int]) -> Int {
    nums = Array(Set(nums)).sorted()
    return nums.count
}

I thought my solution was pretty simple, but 119ms isn't so hot compared with the average of ~60-70ms. Is there a better way to do this?

Answer 1

Your code works correctly, as far as I can see. A small simplification would be

func removeDuplicates(_ nums: inout [Int]) -> Int {
    nums = Set(nums).sorted()
    return nums.count
}

because sorted() can directly be applied to any collection of comparable elements and returns an array.

However, your code does not take advantage of the fact that the given array is already sorted. Two intermediate collections (a set and an array) are created, and the new array is sorted. That can be improved.

Since the array elements are sorted, you can traverse through all elements and only keep those which are different to the previous one. This leads to the following implementation:

func removeDuplicates(_ nums: inout [Int]) -> Int {

    guard let first = nums.first else {
        return 0 // Empty array
    }
    var current = first
    var uniqueNums = [current] // Keep first element

    for elem in nums.dropFirst() {
        if elem != current {
            uniqueNums.append(current) // Found a different element
            current = elem
        }
    }
    nums = uniqueNums
    return uniqueNums.count
}

In addition, you can save memory by overwriting the elements in the given array directly. If a different element is found then it is copied directly to its new position. At the end of the loop, surplus elements are removed:

func removeDuplicates(_ nums: inout [Int]) -> Int {

    guard let first = nums.first else {
        return 0 // Empty array
    }
    var current = first
    var count = 1

    for elem in nums.dropFirst() {
        if elem != current {
            nums[count] = elem
            current = elem
            count += 1
        }
    }

    nums.removeLast(nums.count - count)
    return count
}

In my tests, the last two methods were about a factor 10 faster than yours.