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.

• Adrian: Thank you! I was so excited I could complete the challenge with two lines, only to discover it was slow, slow, slow. Your way of enumerating the array is very elegant. I've never used the dropFirst() subscript like that.