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.

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.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

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

1. Decide variant: converging (two ends) vs same-direction (chase / read-write).
2. 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.
3. 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.
4. Handle edge cases: empty input, all elements rejected, duplicate semantics for "first pair" vs "count pairs".
5. 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.

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.