2SUM problem

26 Dec 2011

2SUM problem

Given an array a[0] ... a[n-1], find 2 elements that sum up to k

Now this is a classic problem. Everybody will certainly say it is O(n^2).

It turns out that there is a O(n log n) solution.

First of all, sort the array. Next, we put pointer p at a[0] and pointer q at a[n-1].

Let's try every possible case:

  • If a[p] + a[q] > k, we should reduce the sum, and the only way to do it is move q backward.
  • If a[p] + a[q] < k, we should increase the sum, and the only way to do it is move p forward.

Now let's see some proof.

If a[p] + a[q] > k, then a[p+i] + a[q] is always greater than k. Therefore, q will never be part of the answer.

If a[p] + a[q] < k, then a[p] + a[q-i] is always less than k. Therefore, p will never be the answer.

And that's it.

Give it a kudos