Weekly Algo: Week 2 — The Two Pointer Algorithm

This week I will be continuing the weekly algo series with the Two Pointer algorithm. We’ll walk through how the algorithm works and then look at an example of it in action.

The Two Pointer algorithm is super handy for comparing elements of a list or array. Essentially it works by setting two ‘pointers’ or references, usually in the form of variables that each point to an index in the array so that we can look at two indices at a time. This is great for comparing values at different indices or even swapping or altering values.

Lets take a look at an example where we are searching an ordered array of integers for a pair with a given sum. Here’s our first example code:

function findPair(array, sum){
let i = 0
let j = array.length – 1
while (i <  j ){
if ((array[i] +array[ j]) === sum) {
return array[i] , array[ j]
} else if ((array[i] + array[ j]) > sum ) {
j--
} else {
i++
 }
}
return ‘no pair found’
}

Looking at this code, we can see that the first thing we do is set our two pointers to be equal to the first and last indices of our array. Then we run while loop which will continue to run until our two pointers meet at the same index, since this means we’ve looked at every value in the array. In our loop we first check if the values at our arrays added together are equal to our given sum. If they are, we’ve found a valid pair and simply return these values. Otherwise, we check if the sum of our two values is greater than our goal sum, if this is the case, we move j back one value. This works because we know our list is ordered, meaning j is starting at the highest value, so we need to move down if our value is too large. As we move j downwards, we will eventually either hit a value that creates a valid pair or find a value where the sum is smaller than our goal. If we hit a too-small value, we know that there is no valid pairing for our i value and move to i forwards to check the next possibility. We can see that happening in the else clause in our code. If we get all the way through our loop without returning a set of values, then there are no valid pairs, so we simply return ‘no pair found’. Because this method only requires us to look at each value in our array once, it’s a lot faster than checking each value against all the other values.

Overall, the Two Pointer algorithm is great for searching arrays efficiently and quickly and is a super useful method to keep in mind as a programmer. It can even be used to reverse or alter an array by swapping or altering values based on the value at the other pointer. Go ahead and try it out for yourself and see all the cool things it can do!