The Two Pointer Technique

It's possible to brute force your way into solving a problem. But doing so leads to an inefficient solution.

One common inefficient, brute force method you might see in the wild is the notorious double loop.

function findpairs(arr, k) {
for (let i = 0; i < arr.length - 1; i++) {
 for (let k = 1 + 1; i < arr.length; k++) {
  }
 }
}

It takes forever to go through every element in an array once, but twice? Forget about it.

Instead of using double loops, consider using what is affectionately known as "The Two Pointer Technique".

---

What is a pointer?

In a for loop, the "i" value is the pointer i.e. it goes through each item in the array.

But we if have 2 pointers we can make different calculations based on the different pointers. It is also much faster than using two for loops as both pointers can move through the array at the same time (don't quote me on this part though).

In the example below, the carot symbol (^) is meant to visualize the two pointer concept. The array is in ascending order, which means the first element is the minimum and the last is the max.

const arr = [ 1, 2, 3, 4, 5, 6]
              ^              ^

While there are perhaps thousands of different combinations of pointers, the most typical combination is to have one start at the beginning, and another to start at the end.

Let' see now how we can solve a simple problem using this two pointer method.

---

The situation

We have an array that is sorted in ascending order, and we want to see if any pair of the elements in the array sum up to X.

const array = [1, 2, 3, 4, 5, 6, 7, 8]
                  ^                 ^
const x = 10

function findPairs(array, x) {
 let start = 0; //set the first element
 let end = array.length - 1; //set the last element

 while (start < end) {
  if (array[start] + array[end] === x) {
   return true; //if any two elements equal x, we are done. 
  } else if (array[start] + array[end] < x) {

 }
}

In the "else if" statement runs, we will change the first pointer to the next element in the array.

We will keep the second element in place, but need to increment the position (start++) of the first pointer.

const array = [1, 2, 3, 4, 5, 6, 7, 8]
                  ^                 ^
const x = 10

function findPairs(array, x) {
 let start = 0; //set the first element
 let end = array.length - 1; //set the last element

 while (start < end) {
  if (array[start] + array[end] === x) {
   return true; //if any two elements equal x, we are done. 
  } else if (array[start] + array[end] < x) {
   start++
  }
 }
}

---

Don't forget your second pointer

This situation above, however, doesn't fully satisfy all conditions. While the array is sorted, if a number is missing from the array it will result in an infinite loop.

This is because once the first pointer has made it through the loop, it will continue to look for the missing number. This search, though, is in vain.

The way we will get around it is by decrementing from the last element in the array.

const array = [1, 3, 4, 5, 6, 7, 8]
                  ^        ^
const x = 10

function findPairs(array, x) {
 let start = 0; //set the first element
 let end = array.length - 1; //set the last element

 while (start < end) {
  if (array[start] + array[end] === x) {
   return true; //if any two elements equal x, we are done. 
  } else if (array[start] + array[end] < x) {
   start++;
  } else {
    else--;
   }
 }
}

---

Return index of the elements

This might seem tricky since there are lots of combinations of elements that can equal the sum of X, but all we need to do is return the start and end instead of returning true.

const array = [1, 3, 4, 5, 6, 7, 8]
                  ^        ^
const x = 10

function findPairs(array, x) {
 let start = 0; //set the first element
 let end = array.length - 1; //set the last element

 while (start < end) {
  if (array[start] + array[end] === x) {
   **return [start, end]**; //if any two elements equal x, we are done. 
  } else if (array[start] + array[end] < x) {
   start++;
  } else {
    else--;
   }
 }
}