Two Pointers

Introduction

An algorithm that uses two pointers.

What is a pointer? A variable that represents an index or position within a data structure (like an array).

Many algorithms just use a single pointer to keep track of a single element.

Using a second pointer opens possibilities, we can make comparisons.

Two pointers at two different positions, we can compare the elements and make decisions.

Such comparisons are made using two nested for-loops.

• n is the length of the data structure
• i and j are two pointers used to compare two elements of an array

for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    compare(nums[i], nums[j]);
  }
}

Strategies

Inward Traversal

Pointers start at the opposite ends of the data structure and move inward to each other.

Pointers move to the center, adjusting their positions based on comparisons, until a condition is met or they meet each other.

Ideal for problems where we need to compare elements from different ends.

Unidirectional Traversal

Pointers start at the same end of the data structure (usually the beginning) and move in the same direction.

They generally serve two different purposes.

Use case is when we want one pointer to find information (usually right pointer) and the other to keep track of information (usually left pointer).

Staged Traversal

We traverse with one pointer, when it lands on an element that meets condition, we traverse with the second pointer.

Both pointers serve different purposes.

First pointer searches something, once found, the second pointer finds additional information concerning the value at the first pointer.

When to use two pointers?

It usually requires a linear data structure, like an array or linked list. Or when the input follows a predictable dynamic like a sorted array.

A predictable dynamic can take many forms, for example, a palindromic string.

Examples

Pair Sum - Sorted

Given an array of integers sorted in ascending order and a target value, return the indexes of any pair of numbers in the array that sum to the target. The order of the indexes in the result doesn't matter. If no pair is found, return an empty array.

Example 1

Input: nums = [-5, -2, 3, 4, 6], target = 7
Output: [2, 3]
Explanation: nums[2] + nums[3] = 3 + 4 = 7

Example 2

Input: nums = [1, 1, 1], target = 2
Output: [0, 1]
Note: Other valid outputs: [1, 0], [0, 2], [2, 0], [1, 2], [2, 1]

Tips

Brute force solution involves checking all possible pairs. This is done using two nested loops, an outer one that traverses the array for the first element, and an inner loop that traverses the rest of the array to find the second element.

function pairSumSortedBruteForce(nums, target) {
  const n = nums.length;

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }

  return [];
}

A two-pointer approach is worth considering here because a sorted array allows us to move the pointers in a logical way.

Let's see how this works in the example below:

First you'll look at the smallest and largest values (the first and the last elements). The sum of these values is 1.

Since 1 is less than the target, we need to move one of the pointers to find a new pair with a larger sum.

• Left pointer:
  • This pointer will always point to a value less than or equal to the values at the right pointer because the array is sorted.
  • Incrementing it would result in a sum greater than or equal to the current sum of 1.
• Right pointer:
  • Decrementing the right pointer would result in a sum that's less than or equal to 1.

We should increment the left pointer to find a larger sum:

Again, the sum of the values at those two pointers (4) is too small. Let's increment the left pointer:

Now, the sum (9) is too large. We should decrement the right pointer to find a pair of values with a smaller sum:

Finally, we found two numbers that yield a sum equal to the target. Let's return their indexes:

We just demonstrated a two-pointer algorithm using inward traversal.

For any pair of values at left and right:

• If their sum is less than the target, increment left.
• If their sum is greater than the target, decrement right.
• If their sum is equal to the target, return left and right.

Implementation

function pairSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];

    // If the sum is smaller, increment the left pointer, aiming
    // to increase the sum toward the target value.
    if (sum < target) {
      left += 1;
    }
    // If the sum is larger, decrement the right pointer, aiming
    // to decrease the sum toward the target value.
    else if (sum > target) {
      right -= 1;
    }
    // If the target pair is found, return its indexes.
    else {
      return [left, right];
    }
  }

  return [];
}