Khuong Khuong - 6 months ago 12
Swift Question

Find the pair in array with condition

Let say I have an array of Int, I want to find a pair of number in this array that the sum of this pair is equal to an number, like so:

func findPair(list: [Int], _ sum: Int) -> (Int, Int)? {
for i in 0..<list.count - 1{
for j in (i+1)..<list.count {
let sumOfPair = list[i] + list[j]
if sumOfPair == sum {
return (list[i], list[j])
}
}
}
return nil
}


The first parameter is an array of Int, the second parameter is an number that we need to compare some pairs in that array.

For example:

findPair([1,2,3,4,5], 7) // will return (2, 5), because 2 + 5 = 7


But the complexity of this algorithm is O(n^2).

Is there any way faster.

Any helps would be appreciated. Thanks.

Answer

Try with this:

func findPair(list: [Int], _ sum: Int) -> (Int, Int)? {
    //save list of value of sum - item.
    var hash = Set<Int>()
    var dictCount = [Int: Int]()
    for item in list {

        //keep track of count of each element to avoid problem: [2, 3, 5], 10 -> result = (5,5)
        if (!dictCount.keys.contains(item)) {
            dictCount[item] = 1
        } else {
            dictCount[item] = dictCount[item]! + 1
        }
        //if my hash does not contain the (sum - item) value -> insert to hash.
        if !hash.contains(sum-item) {
            hash.insert(sum-item)
        }

        //check if current item is the same as another hash value or not, if yes, return the tuple.
        if hash.contains(item) &&
            (dictCount[item] > 1 || sum != item*2) // check if we have 5+5 = 10 or not.
        {
            return (item, sum-item)
        }
    }
    return nil
}
Comments