Find the pair in array with condition

Question

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?

Possibly a duplicate of http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number — ChatterOne, Jun 01 '16 at 09:05

score 3 · Answer 1 · answered Jun 01 '16 at 09:14

3

Try the following approach:

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

low=0;

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

while(low<=high)
{
   if(arr[low]+arr[high]==num)
   {        print(low,high);
            break;
    }
   else if(arr[low]+arr[high]<num)
         low++;
   else if(arr[low]+arr[high]>num)
         high--;

}

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

answered Jun 01 '16 at 09:14

Vatsal Prakash

549
6
17

You are typing too fast, I was in typing same solution (: – Shadow Of Jun 01 '16 at 09:18

score 2 · Answer 2 · edited May 08 '20 at 10:54

2

There surely is much faster O(n log(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 decrement second pointer and go to step 3.*

edited May 08 '20 at 10:54

Satyam

15,012
30
127
238

answered Jun 01 '16 at 09:18

ravi

10,736
1
14
33

2

Sorting is `O(n * log_2(n))`, so the algorithm as a whole must have at least that time complexity, or worse. Can't be `O(n)` – Alexander Dec 29 '16 at 22:08

score 2 · Accepted Answer · answered Jun 01 '16 at 09:25

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
}

Find the pair in array with condition

3 Answers3