An explanation of the two pointer technique (two sum) with a sorted array

The two-pointer technique allows you to iterate through an array and find the two numbers that sum up to the target in the most efficient way possible. The “easiest” way to solve this type of problem (one that comes to mind right away) would be to use a nested for loop where the outer for loop goes over every element in the array and the inner for loop looks at every other element and then compare them to see if they sum up to the target and return them. This, however, would be very inefficient because it would take O(n²) time. The two-pointer technique in comparison uses only O(n) time.

We start off with a pointer at the beginning which we can call left, and a pointer at the end, which we’ll call right. On each iteration, we will move one of the pointers. This is done by comparing the elements where the current pointers are at and seeing if they sum up to the target. The target in this scenario is 5. On the first iteration, the current elements where the pointers are at sum up to 4. Since this is less than the target, we know that everything to the right of the first (left) pointer is bigger than the current value it points to which will get us closer to the target. So the first (left) pointer is now at 1 and the end (right) pointer is at 5. On the second iteration, we compare the current values which are equal to 6. This is bigger than the target, and since we know that everything to the left of the last (right) pointer is smaller than the current value, we move that pointer to the left, at 3. So, once again we compare the current values. 1 and 3 equal 4, so the first (left) pointer must be increased. Lastly, we arrive on 2 and 3 which equal the target so we have our answer.

Above is what I just explained, written in code. We define the two pointers by setting them to the indices of the beginning and end of the given array. Then we implement our logic, if the sum is less than the target, left is incremented and moved to the right to the next element. Conversely, if the sum is greater than the target, we decrement right and move it to the left. Else if we found the sum, we return the indices. Lastly, if we exit the while loop without returning a value, it means that there are no elements in the array that sum to the target, so we return two negative ones.

I hope you learned something from this as it can be applied to many problems and that this helps you in your coding journey!