Two Pointers

How It Works

Two pointers uses a pair of indices that move through a data structure (usually a sorted array) instead of nesting two loops. The pointers can move toward each other (one from the start, one from the end), or move in the same direction at different speeds.

The classic case is finding a pair that sums to a target in a sorted array: start one pointer at index 0 and the other at the last index. If the current sum is too small, move the left pointer right to increase it; if too large, move the right pointer left to decrease it. Because the array is sorted, each move eliminates a whole range of impossible candidates, so you never have to check every pair explicitly.

The same idea generalizes to in-place array operations: one pointer tracks the "write" position for the next valid element, and the other scans forward reading candidates, which is how in-place deduplication and partitioning work.

When To Use It

Look for two pointers when:

• The array is sorted, or sorting it first doesn't break the problem's requirements.
• You need to find a pair, triplet, or subset satisfying a sum/difference/product condition.
• You're comparing values from opposite ends of a structure (smallest vs. largest).
• The brute-force approach is a nested loop over all pairs (O(n^2)), and the sorted order gives you a way to prune search space.
• You need to modify an array in place without extra memory (e.g., remove duplicates, partition around a pivot).

Time & Space Complexity

• Time: O(n) for the two-pointer scan itself. If sorting is required first, it's O(n log n) overall, dominated by the sort.
• Space: O(1): pointers are just indices; no auxiliary data structure is needed.

Pattern Template

function pairWithTargetSum(sortedArr, targetSum) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left < right) {
    const currentSum = sortedArr[left] + sortedArr[right];

    if (currentSum === targetSum) {
      return [left, right];
    }

    if (currentSum < targetSum) {
      left++; // need a bigger sum
    } else {
      right--; // need a smaller sum
    }
  }

  return [-1, -1]; // no pair found
}

Alternative Approaches

• Hash map: for "two sum" on an unsorted array where you need original indices, a hash map storing value-to-index lookups is O(n) time and O(n) space; often better than sorting first since sorting would lose the original indices.
• Brute force: nested loops checking every pair, O(n^2) time, O(1) space. Fine for very small inputs or as a correctness baseline.
• Binary search: for each element, binary search for its complement in the remaining sorted array: O(n log n), strictly worse than two pointers but useful if you can only check membership, not scan linearly.

Common Mistakes

• Using two pointers on an unsorted array without sorting first (or without realizing the problem doesn't require sorted order, in which case a hash map is the right tool instead).
• Getting the loop condition wrong (left < right vs left <= right), which causes either missed pairs or comparing an element against itself.
• Not handling duplicate values correctly when the problem asks for unique pairs/triplets (e.g. 3Sum), which requires explicit skip-duplicate logic after finding a match.
• Moving both pointers when only one should move, which can skip over valid answers.

Pattern Summary

Two pointers replaces nested-loop pair search with a single linear pass by exploiting sorted order: every pointer move rules out a whole range of impossible pairs. It's the go-to pattern for sum/comparison problems on sorted arrays and for in-place array rewriting.