Reduce instances of an object in an array by rule

Question

I have a simple array of a custom objects.

I would like to reduce the array to one instance of each color selected by the largest size.

The solutions I have come up with seem long an unwieldy, what would be the best approach, i've tried looking at reduce and filter but couldn't work out how to apply here.

class foo {

    var color: String
    var size: Int
    var shape: String

    init(color:String, size:Int, shape:String){
        self.color = color
        self.size = size
        self.shape = shape
    }

}

var array = [foo]()

array.append(foo(color: "Blue", size: 2, shape: "Round"))
array.append(foo(color: "Red", size: 3, shape: "Square"))
array.append(foo(color: "Blue", size: 5, shape: "Round"))
array.append(foo(color: "Yellow", size: 1, shape: "Triangle"))
array.append(foo(color: "Blue", size: 1, shape: "Hexagon"))

Answer 1

You can avoid brute-force O(n^2) nested looping (and enumeration) solution by first sorting the array, and thereafter filtering out duplicate colour objects using e.g. hash value lookup (Method 1 below) or clever exclusion with regard to the sorted array (Method 2 below).

Note also class type naming convention (CamelCase): so Foo rather than foo.

Disclaimer: Don't stare yourself blind on the asymptotic complexity notations below, as premature optimization is, depending on the context and intended usage area of your program, generally something of a sin. I've included them below simply to have some measure to compare the different methods by. Choose the one that you think makes most sense to you.

---

Method 1

Worst case...

• time complexity: O(n log n)

• space complexity: O(n)

Where space complexity refers to space used in excess of the array to which the final result is assigned.

• Let Foo conform to Hashable (let hashValue relate to .color property).
• Sort the array of Foo instances w.r.t. decreasing size (.size property).
• Filter the sorted array w.r.t. to first occurrence of each color, using the conformance to Hashable to swiftly use O(1) hash value lookup for existing color in a Foo:Bool dictionary. Adapted from the comments by Airspeed Velocity in the following answer.

---

Method 2 (as proposed by Nikolai Ruhe):

Worst case...

• time complexity: O(n log n)

• space complexity: O(1)

• Sort the array on color (primary) and size (secondary).
• Filter the sorted array for elements that has a different color than their predecessors.

---

For a third (probably the best one for this application) method, see Nikolai Ruhe:s answer below, presenting a method with O(n)/O(n) time/space worst case complexity, respectively.

---

Implementations

[This step is only needed for Method 1] Conform Foo to Hashable and Equatable:

/* Let Foo conform to Hashable */
class Foo : Hashable {

    var color: String
    var size: Int
    var shape: String

    init(color:String, size:Int, shape:String){
        self.color = color
        self.size = size
        self.shape = shape
    }

    var hashValue: Int {
        return color.hashValue
    }

}

/* And Equatable */
func ==(lhs: Foo, rhs: Foo) -> Bool {
    return lhs.color == rhs.color
}

Set up and example for the filter method(s) that follows shortly:

/* Foo array example */
var array = [Foo]()

array.append(Foo(color: "Blue", size: 2, shape: "Round"))
array.append(Foo(color: "Red", size: 3, shape: "Square"))
array.append(Foo(color: "Blue", size: 5, shape: "Round"))
array.append(Foo(color: "Yellow", size: 1, shape: "Triangle"))
array.append(Foo(color: "Blue", size: 1, shape: "Hexagon"))

Filter as per your specifications:

/* Method 1 (assumes Foo conforms to Hashable (& Equatable))   */
var addedDict = [Foo:Bool]()
var arrFiltered = array.sort{ $0.0.size > $0.1.size }
    .filter {addedDict.updateValue(true, forKey: $0) == nil }

/* Method 2 (as proposed by Nikolai Ruhe)                      */
var previousColor: String?
let arrFiltered = array.sort{ $0.color == $1.color ? $0.size > $1.size : $0.color < $1.color }
    .filter{ if $0.color != previousColor { previousColor = $0.color; return true }; return false }
    /* condensed .filter solution by @Nikolai Ruhe, thanks! */

Result:

for bar in arrFiltered {
    print(bar.color, bar.size)
}

/* Blue 5
   Red 3
   Yellow 1 */

The sorting step is the dominant step in this solution (for both methods). From swift/stdlib/public/core/Sort.swift.gyb, it seems as if Swift uses introsort (specifically, a hybrid of introsort combined with insertion sort), running in, worst case, as O(n log n).

Answer 2

let result = Set(array).flatMap { color in array.filter { $0 == color }.maxElement { $0.0.size < $0.1.size } }

A combination of Set and maxElement.

Since I used the examples of dfri's answer, it should be noted that the objects in array should conform to Hashable and Equatable. The answer is made just to show an alternative and personally I think the answer of dfri is a lot better (and faster).

Answer 3

Here's a simple and very performant solution that does not need Hashable or any other modifications on Foo:

var biggestFoos = [String: Foo]()
for foo in array where biggestFoos[foo.color]?.size < foo.size {
    biggestFoos[foo.color] = foo
}
let result = Array(biggestFoos.values)

Answer 4

You can try this method using filter, but it can be time-consuming when you array is huge since you have to iterate through the array for each element.

let arrayFiltered = array.filter { (fooElement) -> Bool in
    for (idx, fooItem) in array.enumerate() {

        if fooItem.color == fooElement.color && fooItem.size > fooElement.size {
            return false
        }
    }
    return true
}