Algorithms - Two Pointers Pattern

This covers the Two Pointer Pattern algorithm for technical interviews in JavaScript.

When to Use the Two Pointer Pattern

The Two Pointer Pattern is helpful when you need to perform a search to find a pair of numbers that meet a certain condition within a sorted data set.

For example, you can use this method to solve to find the first two numbers in an array that sums to a desired value.

The Two Pointer Pattern only works if your data set is sorted. Be sure to ask your interviewer if the data set is already sorted or if it can be.

How to Use the Two Pointer Pattern

Let's assume you are solving to find the first set of numbers that sum to zero in a sorted array.

Instead of using brute force and nested loops to check the 1st item with the 2nd, then the 1st item with the 3rd and so on, you can set up pointers in the first (left) and last (right) position of the array to compare.

Move the pointers based on the sum of the values:

If the sum of the pointers are greater than the solve for 0, it means the highest number is too large, so move the last pointer (right) down 1 position.
If the sum of the pointers are less than the solve for 0, it means your smallest number is too small, so move the first pointer (left) up 1 position.

Repeat this logic until the pointers meet or you solve for the desired sum.

Hasn't clicked yet?

If the biggest number (right pointer) is paired with the smallest number (left pointer) and their sum is greater than the desired value, then no other number paired with the right pointer will result in the desired sum as it will continue to be too high. So, move the right pointer one position over towards the center, keep the left pointer the same, and run through the iteration again.

The same idea applies if the sum of the pointers is too small - you move the left pointer over one spot towards the center. If the sum of smallest number (left pointer) and largest number (right pointer) is less than the sum, then there is no number remaining in the array that can be paired with the smallest number to meet your desired sum - since even paired with the highest number is too low.

Visual Examples

In this example, we solve for the first pair that sums to 0. Notice that the data set is sorted from smallest to largest.

If you take the first number at index 0 (-3) and the last number at index 6 (3), you'll find the answer in one iteration - the sum equals zero!

What if you are solving for the first pair that sums to 2? This completes in 3 iterations.

Here's another example, solving for sum of 10. Completes in 5 iterations:

Last example, solving for sum of 30. Here, the solution is not found and it uses the max amount of iterations, 4:

How to Code Two Pointer Solution

Example: return an array of the first pair that sums to zero.

function zeroSum(arr) {
   let left = 0;
   let right = arr.length - 0;

   while(left < right){
      let sum = arr[left] + arr[right];
      if (sum === 0){
         return [[arr[left], arr[right]];
      } else if (sum > 0){
         right --;
      } else {
         left ++;
      }
   }
}

Explain the Code Line by Line

function zeroSum(arr) {
  ...
}

Declare the JavaScript function, passing in arr as a parameter for a data set.

   let left = 0;
   let right = arr.length - 0;

Here we declare our pointer's initial index.
The left pointer will always start at 0, since an array's index starts at 0.
The right pointer starts at the last index in our array, which we find by getting the array length and subtracting by 1 to get it's index.

   while(left < right){
     ...
   }

We set our loop to run only while our left pointer is less than our right pointer. Otherwise we'd duplicate iterations if our left pointer is greater than or equal to the right pointer.

      let sum = arr[left] + arr[right];

We declare sum inside the while loop so that the respective pointers update on each iteration.
The sum equals the value at the left pointer's index plus the value at the right pointer's index.

      if (sum === 0){
         return [[arr[left], arr[right]];
      } else if (sum > 0){
         right --;
      } else {
         left ++;
      }

The if statement sets the pointers based on our condition.
First, if the sum equals 0, then return the values in an array itself. This return will exit the while loop on the first iteration that matches our criteria.
If sum is greater than 0, then the numbers are too large. Decrease the right pointer one space to the left.
Else (if sum is less than 0), then the numbers are too small. Increase the left pointer one space to the right.

Big O of the Two Pointer Pattern

Using brute force with nested loops gives a time complexity of O(n^2) as you have to loop through each item in the array to grab the 1st number, then loop again through each item to check it against the 2nd.

Using the Two Pointer Pattern reduces the time complexity to be more favorable at O(n). This pattern will at most only iterate the length of the array minus 1, since we compare in pairs.

Space to solve this problem will be constant at O(1).