26 Dec 2011

```
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.