Remove duplicates from array of Int in Swift (for-in-loop)

Question

There are a lot of methods to remove duplicates from an array in swift, but I'm trying to use a for in loop to manage that. Can any one explain, why this code doesn't work?

Fatal error: Index out of range

func deleteDuplicates(array: [Int]) -> [Int] {

    var newArray = array

    for i in 0 ..< newArray.count - 1  {
        for j in i + 1 ..< newArray.count  {

            if newArray[i] == newArray[j] {
                newArray.remove(at: j)
            }
        }
    }
    return newArray
}

array1 = [0, 1, 8, 3, 4, 4, 3, 6, 7, 11, 4, 5, 5, 8]
deleteDuplicates(array: array1)

Answer 1

The problematic part is to iterate over an array and update that array at the same time. In this case, removing an element while iterating.

Removing an element decreases array length (count) and also changes indices. Therefore in

for j in i + 1 ..< array.count  {
    if array[i] == array[j] {
        newArray.remove(at: j)
    }
}

After removing the first index, your other indices become invalid. Note that count is always read only once, before the actual iteration.

This is one of the reasons why removing elements during iteration is dangerous and complicated. You could fix it by maintaining the number of removed elements and update indices accordingly. Or you can iterate backwards:

var newArray = array

for i in (0 ..< newArray.count - 1).reversed()  {
    for j in (i + 1 ..< newArray.count).reversed()  {
        if newArray[i] == newArray[j] {
            newArray.remove(at: j)
        }
    }
}
return newArray

You are still changing indices and count but since you are iterating backwards, you only change the indices that have been already used.

In general it's simple and safer to build a new array instead of updating the current one:

var newArray: [Int] = []

for value in array {
    if !newArray.contains(value) {
       newArray.append(value)
    }
}

return newArray

which can be very reduced in complexity (performance) by using a Set to keep added elements:

var newArray: [Int] = []
var foundElements: Set<Int> = []

for value in array {
    if foundElements.insert(value).inserted {
       newArray.append(value)
    }
}

return newArray

Which can be simplified using filter:

var foundElements: Set<Int> = []
return array.filter { foundElements.insert($0).inserted }