Introduction to Two Pointers

Nested loops were my go to solution for array problems until I discovered the two pointers technique. Two indices can remove whole groups of impossible pairs when the input has useful ordering.

Pointer movement

Two pointers are indices or references that traverse a data structure together, apart, or at different speeds. The movement rule is the important part. It must use a property of the input, such as sorted order, to avoid revisiting pairs.

I was trying to find two numbers in a sorted array that sum to a target. My first attempt used nested loops:

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

This checks every pair, so the time complexity is O(n²).

Sorted scan and safe moves

Because the array is sorted, I can start from both ends and move inward:

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

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

    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++; // Need a larger sum, move left pointer right
    } else {
      right--; // Sum too large, move right pointer left
    }
  }

  return []; // No solution found
}

If the sum is too small, every remaining pair with the current left value is also too small. The algorithm advances left. If the sum is too large, every remaining pair with the current right value is also too large. The algorithm decreases right. Each pointer moves in one direction, so the scan takes O(n) time and O(1) extra space.

Uses and a movement rule

I find the pattern useful for sorted pair or triplet searches, palindrome checks from both ends, partitioning, and fast and slow cycle detection. The movement rule changes with the problem, but the goal is the same: eliminate candidates instead of testing them all.

Two pointers taught me to look for a monotonic decision before writing nested loops. Sorted data often provides exactly the evidence needed to move one side without losing a valid answer.

Two pointers can reduce a pairwise search from O(n²) to O(n) when the input supports a safe movement rule. Before using the pattern, identify the ordering or invariant that justifies each pointer update.