The Two Sum Problem

Part 1: A Swifty Solution

Here’s the problem.

Given an array of numbers, say [2,3,3,4,5,6] and a target number, say 9, how can you find the two numbers that equal 9, then return the array indexes of the two values.

So, the first thing you want to do is unique the array. There are two ways to do that: first, use Array(Set) to cast the array to a Set and back again to an Array. This eliminates duplicates, but the set is disordered and so the array is unlikely to have the same order as before. That may or may not matter.

If the order does matter, then the second way to do it is to create an extension to Array that retains the order of the first array, although of course with collapsing, not all values will have the same index as before.

(The extension was pulled from a Stack Overflow post but apparently it’s now in swift-algorithms too.)

I show both functions here.

Now comes the problem of performance.

First, I calculate the number I’m looking for — the current value subtracted form the target number gives it to me. So if the current number pulled out from the array in the loop is 1, and the target is 5, then the number I’m looking for is 4.

The fastest way to find the index of a value in an array is with arr.firstIndex(of:), but that iterates through every element until it finds the matching value, so it’s still linear O(n).

So first you want to find out if you should bother looking. I accomplish that here by adding each array entry to a Dictionary hash table. Then on each loop you can use dict.contains(value) to see if the value exists, before you go to retrieve it’s index from the array. If the value doesn’t exist in the Dictionary, then the array search is never performed.

import UIKit

var greeting = "Hello, playground"

var myNums = [4,9,3,3,2,4]
var myTarget = 5

// this works where order of array doesn't matter


// from swift algorithms, uniqued but ordered
extension Array where Element: Hashable {
    func uniqued() -> Array {
        var buffer = Array()
        var added = Set<Element>()
        for elem in self {
            if !added.contains(elem) {
                buffer.append(elem)
                added.insert(elem)
            }
        }
        return buffer
    }
}

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        let uNums = Array(Set(nums)) //uniqued, disordered
        print("uniqued with Array(Set) disordered \(uNums)")
        var hm = [Int: Int]()
        for num in uNums.enumerated() {
            let diff = target - num.element
            if hm.contains {$0.value == diff } {
                let n = uNums.firstIndex(of: diff)! as Int
                return [num.offset, n] 
            }
            hm[num.offset] = num.element // add for next loop
        }
        
        return [0] // we found no numbers that summed to target
         
    }
    func twoSumOrdered(_ nums: [Int], _ target: Int) -> [Int] {
        let uNums = nums.uniqued() //uniqued, ordered
        print("uniqued ordered \(uNums)")
        var hm = [Int: Int]()
        for num in uNums.enumerated() {
            let diff = target - num.element
            if hm.contains {$0.value == diff } {
                let n = uNums.firstIndex(of: diff)! as Int
                return [num.offset, n]
            }
            hm[num.offset] = num.element
        }
        
        return [0]
         
    }


}

NOTE although the contraint makes it clear you have to eliminate duplicates, it’s not so clear about multiple answers, say 3 + 2 and 1 + 4 both equal 5 in the same array.

Coming: Part 2: Higher Order Function Solution.