Find the pair in array with condition

Khuong Source

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?



answered 2 years ago Vatsal Prakash #1

Try the following approach:

sort(arr,arr+n);//Sort the array


high=n-1; // The final index number (pointing to the greatest number)

   {        print(low,high);
   else if(arr[low]+arr[high]<num)
   else if(arr[low]+arr[high]>num)


Basically, you are following the greedy Approach over here... Hope it works.. :)

answered 2 years ago ravi #2

There surely is much faster O(n) to solve this problem. Below is the pseudo algorithm for that :-

1) Sort the given array.
2) Take two pointers. One pointing to the beginning and other pointing to the end.
3) Check if sum of two values pointed by two pointer is equal to given number.
4) If yes then return.
5) If greater than increment first pointer and go to step 3.
6) Else increment second pointer and go to step 3.*

answered 2 years ago Duyen-Hoa #3

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) {

        //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 powered by Disqus