Sunday, January 16, 2011

Number of pairs whose sum equals k

You have an integer array and a number k, find all the pairs of numbers from the array whose sum is equal to k.
What will be the approach if the numbers in the given array are sorted and unsorted?



Approach: 
There are myraid number of approaches to attack this problem.
Lets take the case when the array is already sorted.
One of the approaches can be to iterate over each element let say a[i] = x, then we need to figure out if a number k - x exists or not in the array

We can very well search for the element in the array in O(n) making the overall complexity O(n^2).
But wait, since the array is already sorted we could have just performed a binary search over the array to search a given element.
This reduces the overall complexity to O(n*logn)

Can we improve the approach?
Well, there is an important observation that if we pick the two extreme indexes of the array and sum it up, there are 3 possibilities

1. Sum is equal, bingo :)
2. Sum is less than the target k, 
3. Sum is greater than target k

For the case 2, if there exists a pair, it has to be achieved by increasing the sum, i.e by moving the left index ahead.
For the case 3,  if there exists a pair, it has to achieved by decreasing the sum, i.e by moving the right index behind.
For the case 1, you can move any index.
Following the above approach you can figure out all the possible combinations.

So how about the time complexity?
Each element is accessed only once, hence the overall complexity turns out to be linear O(n)
Below piece of code just does the job


void printPairs(int *arr, int n, int k) {
    if (n < 2)
       return;
    int front = 0, back = n - 1;
    while (front < back) {
        if (arr[front] + arr[back] == k) {
           cout << front << " " << back << endl;
           if (back > 0 && arr[back - 1] == arr[back]) back--;
           else front++;
        } else if (arr[front] + arr[back] < k) {
            front++;
        } else {
            back--;
       }
    }
}


In case the array is not sorted?
Well we can sort the array in O(nlogn) and then apply one of the above approaches, the overall complexity would be O(nlogn)

But is it necessary to sort?
If you have the luxury, you can easily push the elements in the hash, and then look for each element x, if there exists an element k - x?
Safely assuming the Insertion and lookup complexity of the hash implemention to be O(1), the overall complexity of the algorithm would be O(n)

5 comments :

  1. This problem has ambiguities. Where do the number pairs come from? Are they from members in the array? Are they already paired? Must a pair have unique values from another pair to be counted? In what circumstances is a number pair greater than a given number?

    ReplyDelete
  2. Pairs are obviously from the array element .... a number pair is greater if the sum of the pair is higher ... no restriction on pairing of elements ...
    Regards

    ReplyDelete
  3. For sorted array:(ascending order)
    Take two pointers p and q,P->first element of the array and q->last element of the array.
    If a[p]+a[q]>=k then all the pairs {(a[p],a[q]),......(a[q-1],a[q]) are the pairs
    then q=q-1;
    else p=p+1;
    Repeat this process till p<=q

    ReplyDelete
  4. Is there any more optimized approach than the above?

    ReplyDelete
  5. yeah .. correct approach for the sorted array case ...

    ReplyDelete