01. Two Pointers

TL;DR

Scan a linear sequence with two indices that move according to a rule—either toward each other from both ends (leveraging sortedness or symmetry) or in the same direction (read/write or chase). The pattern turns many (O(n^2)) pair explorations into (O(n)) when an ordering or partition invariant lets you discard whole ranges per step.

Core Basics

Object: two indices (or one read / one write) on a linear sequence; each advance should discard a family of candidate tuples, not just one element.
Winning structure: sorted data for converging pointers (monotone sum/area), or a stable partition invariant for same-direction scans.
Staff-level bar: narrate why the rejected side can never contain the answer (non-crossing pairs, order preservation, or closure under the predicate).

Recognition Cues

Phrases: "sorted array", "pair whose sum is …", "in-place", "remove duplicates", "merge two sorted", "palindrome", "container / water / area", "subsequence".
Shapes: sorted or sortable array; two sequences walked together; need linear pass with two roles (reader vs writer, left boundary vs right boundary).
When sorting first is allowed, opposite pointers often appear after the sort; same-direction pointers often avoid extra space on already ordered data.

Use-case Lens

Best when: two positions in a linear sequence can move monotonically and each move discards a whole set of impossible candidates.
Not for: unsorted pair search where moving one side does not prove anything; use hash maps or sorting first.
Main invariant: after each pointer move, every discarded index/pair is impossible under the ordering or partition rule.
Interview move: say whether you are using opposite pointers for sorted pair logic or same-direction pointers for stable compaction/merge.

Diagram

Loading diagram…

Step-by-step Visual

Example: sorted values = [1, 2, 4, 6, 8], target 12.

Loading diagram…

The pointer movement is not random. In sorted data, if the sum is too small, moving right left would only make it smaller; only left++ can help.

Understanding

Opposite pointers maintain a monotone squeeze: as the left index moves right, the only viable partner for many queries shifts left on the right side—true when values are ordered so larger sums come from moving right inward, smaller sums from moving left inward. Same-direction pointers encode partitioning: a slow boundary separates "finalized prefix" from "unprocessed suffix"; a fast scanner commits elements that satisfy a predicate.

Generic Recipe

Decide variant: converging (two ends) vs same-direction (chase / read-write).
For converging: sort if needed; initialize left, right; loop while left < right; compare a function of values[left], values[right] to the target; advance the side that preserves the sorted invariant toward the answer.
For same-direction: initialize writeIndex (or slow) and scanIndex (fast); iterate scanIndex through the array; when an element should stay, assign it at writeIndex and advance writeIndex.
Handle edge cases: empty input, all elements rejected, duplicate semantics for "first pair" vs "count pairs".
Return the required aggregate (index pair, count, new length, or filled prefix).

Complexity

Time: usually (O(n)) per pass after an optional (O(n \log n)) sort for converging patterns on unsorted input.
Space: (O(1)) extra for in-place two-pointer; (O(\log n)) to (O(n)) if sorting copy or recursion matters.

Memory Hooks

Operational mantra: order the candidates, compare the ends, then move the pointer whose side can no longer win.
Anti-panic: ask "are the candidates ordered?" If yes, prove which side can move because all skipped pairs are dominated.

Study Pattern (SDE3+)

Recognition drill (10 min): classify five problems as converging pointers, same-direction compaction, or sort-then-scan.
Implementation sprint (25 min): code one pair-sum and one in-place partition; say the discard rule before each pointer move.
Staff follow-up (10 min): discuss what changes when input order must be preserved or sorting would lose original indices.

Generic Code Template

Go

package main

// Opposite pointers on sorted ascending slice: first pair summing to target (1-based indices idea).
func twoSumPairOnSorted(values []int, target int) (int, int, bool) {
	left := 0
	right := len(values) - 1
	for left < right {
		currentSum := values[left] + values[right]
		switch {
		case currentSum == target:
			return left, right, true
		case currentSum < target:
			left++
		default:
			right--
		}
	}
	return -1, -1, false
}

// Same-direction: compact slice keeping relative order; predicate keeps nonzero values.
func moveNonZeroesStable(values []int) []int {
	writeIndex := 0
	for scanIndex := range values {
		if values[scanIndex] != 0 {
			values[writeIndex] = values[scanIndex]
			writeIndex++
		}
	}
	for padding := writeIndex; padding < len(values); padding++ {
		values[padding] = 0
	}
	return values
}

func main() {}

JavaScript

// Opposite pointers on sorted array: pair summing to target.
function twoSumSorted(values, target) {
  let left = 0;
  let right = values.length - 1;
  while (left < right) {
    const currentSum = values[left] + values[right];
    if (currentSum === target) {
      return { left, right, found: true };
    }
    if (currentSum < target) {
      left += 1;
    } else {
      right -= 1;
    }
  }
  return { left: -1, right: -1, found: false };
}

// Same-direction in-place dedupe on sorted array; returns new logical length.
function uniqueCountSorted(sortedValues) {
  if (sortedValues.length === 0) {
    return 0;
  }
  let writeIndex = 1;
  for (let scanIndex = 1; scanIndex < sortedValues.length; scanIndex += 1) {
    if (sortedValues[scanIndex] !== sortedValues[writeIndex - 1]) {
      sortedValues[writeIndex] = sortedValues[scanIndex];
      writeIndex += 1;
    }
  }
  return writeIndex;
}

Variants

Opposite / converging — two ends on a sorted (or monotonic) array: two-sum II, 3Sum outer loop + inner pair, container with most water, trapping rain (with max-so-far variant).
Same-direction read/write — dedupe sorted array, remove element, move zeroes, merge sorted into first array: one pointer commits, one scans.
String / Unicode — skip non-alphanumeric or normalize case while advancing from both ends (palindrome checks).

Representative Problems

167. Two Sum II — Input Sorted — opposite pointers on sorted array
011. Container With Most Water — converging with area objective
015. 3Sum — sort then outer index plus inner pair
283. Move Zeroes — same-direction stable partition
125. Valid Palindrome — symmetric scan with filtering

Anti-patterns

Using converging two-pointer without sortedness or a replacement invariant—random order breaks the squeeze logic unless you sort first or use another structure (hash map for two-sum on unsorted).
Advancing both pointers unconditionally when only one side is safe to move (two-sum–style problems).
Confusing index after loop with inclusive/exclusive length when returning "new size" for in-place writes.
Same-direction: forgetting to fill trailing slots when the problem requires zeros or truncation semantics.

On this page