0
$\begingroup$

Problem statement- Given a sorted array, print out the pair of elements of the array that have a sum of K, where K is a whole number. The solution to the above problem goes like this:

With using the Two Pointers pattern, and Pointer 1 pointing to the beginning of the array and Pointer 2 pointing to the end of the array, we will check if the numbers pointed by the pointers add up to the target sum. If they do, we have found our pair. If not, we should do one of these things:

If the sum is bigger than the target sum, this means that we need a smaller sum so, we are going to decrement the Pointer 2 (end-pointer).

If the sum is smaller than the target sum, this means that we need a bigger sum so, we are going to increment the Pointer 1 (start-pointer).

What I fail to understand in the above solution is: If the sum is bigger than the target sum, why is decreasing the Pointer 2 position the only way? Why can't we decrease Pointer-1 position?

$\endgroup$

2 Answers 2

0
$\begingroup$

Consider a situation where Pointer 1 is equal to $i$ and Pointer 2 is equal to $j$, and $A[i] + A[j] > K$.

The last time Pointer 1 was incremented, Pointer 2 was in a position $j' \geqslant j$. Since it was Pointer 1 which was modified, that means that $A[i-1] + A[j'] < K$. Since the array is sorted, $A[j] \leqslant A[j']$. Therefore, there is no need to decrement Pointer 1, because $A[i-1] + A[j] \leqslant A[i-1] + A[j'] < K$.

$\endgroup$
0
$\begingroup$

For every position of the left pointer, there is a unique position of the right pointer such that the sum exceeds or equals $K$ and moving the right pointer to the left makes the sum smaller than $K$, and symmetrically.

E.g. $2,5,6,8,11,15,21$, target sum $14$. We show the unique right positions for increasing left positions:

$\mathbf2,5,6,8,11,12,14,\mathbf{15},21\\ 2,\mathbf5,6,8,\mathbf{11},12,14,15,21\\ 2,5,\mathbf6,\mathbf8,11,12,14,15,21$

The two-pointer algorithm works by finding these unique positions, because as you can see no backtracking is ever necessary.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.