Proving that two pointer approach works(Pair sum ques.)

Question

I was trying to solve the pair sum problem, i.e., given a sorted array, we need to if there exist two indices i and j such that i!=j and a[i]+a[j] == k for some k.

One of the approaches to do the same problem is running two nested for loops, resulting in a complexity of O(n*n).

Another way to solve it is using a two-pointer technique. I wasn't able to solve the problem using the two-pointer method and therefore looked it up, but I couldn't understand why it works. How do I prove that it works?

#define lli long long
 //n is size of array
bool f(lli sum) {
    int l = 0, r = n - 1;
    while ( l < r ) {
       if ( A[l] + A[r] == sum ) return 1;
       else if ( A[l] + A[r] > sum ) r--;
       else l++;
    }
    return 0;
}

Answer 1

Well, think of it this way:

You have a sorted array (you didn't mention that the array is sorted, but for this problem, that is generally the case):

{ -1,4,8,12 }

The algorithm starts by choosing the first element in the array and the last element, adding them together and comparing them to the sum you are after.

If our initial sum matches the sum we are looking for, great!! If not, well, we need to continue looking at possible sums either greater than or less than the sum we started with. By starting with the smallest and the largest value in the array for our initial sum, we can eliminate one of those elements as being part of a possible solution.

Let's say we are looking for the sum 3. We see that 3 < 11. Since our big number (12) is paired with the smallest possible number (-1), the fact that our sum is too large means that 12 cannot be part of any possible solution, since any other sum using 12 would have to be larger than 11 (12 + 4 > 12 - 1, 12 + 8 > 12 - 1).

So we know we cannot possibly make a sum of 3 using 12 + one other number in the array; they would all be too big. So we can eliminate 12 from our search by moving down to the next largest number, 8. We do the same thing here. We see 8 + -1 is still too big, so we move down to the next number, 4, and voila! We find a match.

The same logic applies if the sum we get is too small. We can eliminate our small number, because any sum we can get using our current smallest number has to be less than or equal to the sum we get when it is paired with our current largest number.

We keep doing this until we find a match, or until the indices cross each other, since, after they cross, we are simply adding up pairs of numbers we have already checked (i.e. 4 + 8 = 8 + 4).

This may not be a mathematical proof, but hopefully it illustrates how the algorithm works.