Remove duplicates from a multi-dimensional array

Question

I wrote the following extension to remove duplicates from my Array.

extension Array where Element : Equatable{

    func removeDups() -> [Element]{
        var result = [Element]()

        for element in self{
            if !result.contains(element){
                result.append(element)
            }
        }

        return result
    }
}

Linear Array

let linearArr = [1,2,2,3]
linearArr.removeDups() // [1,2,3] works well!

Multi dimensional Array

let multiDimArr : [[Int]] = [[1,2,3], [1,2,3], [1,2 ,4]]
multiDimArr.removeDups() // Error!

Type [Int] does not conform to Equatable

I read here. And the answer says Array comparisons using == should work. It doesn't work all the time:

Works

if (["1", "2"] == ["1", "2"]){
    print("true")
}

Doesn't work

if ([1, 2] == [1, 2]){ // ERROR!
    print("true")
}

Ambiguous use of operator '=='

This is peculiar. I can compare Array of Strings but can't compare Array of Ints.

I also saw this comment:

The reason myArray1 == myArray2 is that NSObject conforms to Equatable, calling -[equals:] to conduct the test

Not sure if the ☝️ comment is still valid.

To summarize:

• Are arrays equatable? Can I compare them using ==
• Why is it different for comparing Array of Strings vs. Array of Ints
• How can I remove duplicates from a multi-dimensional array?

I'm currently working with Swift 4.0.2

Privilege

I'm not sure but I think Swift 4.1 adds support for [Int] being Equatable. – Sunderance

Looks like it @Sunderance github.com/apple/swift-evolution/blob/master/proposals/… – Lactoscope

@Sunderance is correct – in Swift 4.1, Array<Element> conforms to Equatable when Element conforms to Equatable, so multiDimArr.removeDups() will compile in 4.1 provided you relax your (currently over-constrained) extension to where Element : Equatable. – Quatrain

The fact that [1, 2] == [1, 2] doesn't compile is the bug SR-5944, the compiler is considering it to be ambiguous due to == overloads for IndexSet and IndexPath (both of which are ExpressibleByArrayLiteral). But Swift should default an array literal to Array though, resolving the ambiguity. Saying [1, 2] as [Int] == [1, 2] or not importing Foundation resolves the issue. – Quatrain

@Quatrain interesting. About your 2nd comment. Both your solutions work on 4.0.2. About your 1st comment. provided you relax your (currently over-constrained. I actually intended it to be Equatable. (I'll edit it now). There is no reason to have it be for Comparable. And is this any different for Swift 3? – Privilege

@Honey The bug report says that [1, 2] == [1, 2] used to compile in Swift 3, but I haven't verified that for myself. – Quatrain

Your code works for me in Xcode 9.3... – Midday

Slight pedantic nitpick: [[1,2,3], [1,2,3], [1,2 ,4]] is not a multidimensional array – it's a nested array (true multidimensional arrays enforce that the dimensions are of consistent sizes). – Quatrain

Checking contains against an Array like that leads this to have O(N^2) performance :( – Doradorado

@Doradorado yes. But I don't know of a better way to remove dups. [Int] not hashable...meaning you can't do something like let removedDups = Array(Set(originalArray)). Is there a better way? – Privilege

@Honey As others said, update to Swift 4.1. [Int] becomes hashable – Doradorado

Answer 1

Are arrays equatable? Can I compare them using ==

Prior to Swift 4.1, Array didn't conform Equatable. There was however an overload of == that compared two arrays with Equatable elements, which is what enabled this to compile:

if ["1", "2"] == ["1", "2"] { // using <T : Equatable>(lhs: [T], rhs: [T]) -> Bool
    print("true")
}

However in Swift 4.1 (available with Xcode 9.3), Array<Element> now conforms to Equatable when its Element conforms to Equatable. This change is given in the changelog:

Swift 4.1

[...]

• SE-0143 The standard library types Optional, Array, ArraySlice, ContiguousArray, and Dictionary now conform to the Equatable protocol when their element types conform to Equatable. This allows the == operator to compose (e.g., one can compare two values of type [Int : [Int?]?] with ==), as well as use various algorithms defined for Equatable element types, such as index(of:).

Your example with multiDimArr.removeDups() compiles and runs as expected in 4.1, yielding the result [[1, 2, 3], [1, 2, 4]].

In Swift 4.0.3, you could hack it by adding another overload of removeDups() for nested arrays:

extension Array {
  func removeDups<T : Equatable>() -> [Element] where Element == [T] {

    var result = [Element]()

    for element in self{
      if !result.contains(where: { element == $0 }) {
        result.append(element)
      }
    }

    return result
  }
}

let multiDimArr = [[1, 2, 3], [1, 2, 3], [1, 2, 4]]
print(multiDimArr.removeDups()) // [[1, 2, 3], [1, 2, 4]]

This does unfortunately lead to some code duplication, but at least you'll be able to get rid of it when updating to 4.1.

The fact that this example doesn't compile in either 4.0.3 or 4.1:

if [1, 2] == [1, 2] { // error: Ambiguous use of operator '=='
    print("true")
}

is due to the bug SR-5944 – the compiler is considering it to be ambiguous due to == overloads for IndexSet and IndexPath (both of which are ExpressibleByArrayLiteral). But Swift should default an array literal to Array though, resolving the ambiguity.

Saying either:

if [1, 2] as [Int] == [1, 2] {
    print("true")
}

or not importing Foundation resolves the issue.

---

Finally, it's worth noting that the performance of removeDups() can be improved if the Element type is also Hashable, allowing it to run in linear, rather than quadratic time:

extension Array where Element : Hashable {

  func removeDups() -> [Element] {
    var uniquedElements = Set<Element>()
    return filter { uniquedElements.insert($0).inserted }
  }
}

Here we're using a set to store the elements that we've seen, omitting any that we've already inserted into it. This also allows us to use filter(_:), as @Alexander points out.

And in Swift 4.2, Array also conditionally conforms to Hashable when its Element is Hashable:

Swift 4.2

[...]

• SE-0143 The standard library types Optional, Array, ArraySlice, ContiguousArray, Dictionary, DictionaryLiteral, Range, and ClosedRange now conform to the Hashable protocol when their element or bound types (as the case may be) conform to Hashable. This makes synthesized Hashable implementations available for types that include stored properties of these types.

Quatrain

And you can use filter :) https://mcmap.net/q/92418/-removing-duplicate-elements-from-an-array-in-swift – Doradorado

@Quatrain I need same functionality for Swift 3.0 so what i need to changes – Ardithardme

OMG! Hamish, you just saved me hours of coding!!! How can I donate to your cause? :) – Lapointe

@Lapointe Happy to be of help! I don't have a place where you can donate, but you're welcome to upvote the answer if you feel it was useful :) – Quatrain

@hamish: I did upvote then :) Just one question to the last code block ( beginning with >>extension Array where Element : Hashable {<<): Is it correct that the result is not necessarily ordered like the original array? – Lapointe

@Lapointe No, it preserves the order of the original array, because it uses filter which iterates sequentially through an array. – Quatrain

Thanks @Hamish. You're the best! – Lapointe

Answer 2

This is a place where recursion would solve the problem. Have you considered recursion? I was going to answer the question with actual code, but I don't know the syntax for Swift. so, here is some pesudocode:

function removeDupes() {
    buffer = array;
    foreach this->elements as key => element {             
         if(element is type array) {
              this->elements[key] = element->removeDupes();
         } else {
              if(!this->contains(element)) {
                  buffer->add(element);
              }
         }             
    }
    return buffer;
}

Basically, you want to test if the element itself is an array. If it is, then you want to call that array's removeDupes() method (which in turn will look for duplicates, unless it finds another array, then it will call itself again).

Ermentrude

I'm not asking for psuedocode. Problem is Array of Ints not being Equatable... – Privilege