Two Pointers

Two Pointers solves a problem by moving two or three indexes through the input with a rule that proves each move is safe. The goal is to avoid repeated scans by discarding impossible candidates as soon as the current pointer state tells us enough.

Quick Identifier

• Topic: two-pointers
• Pattern: Two Pointers
• Core Question: Can moving one pointer safely eliminate many candidates?
• Common Shapes: Inward convergence, sorted target sum, slow/fast overwrite, subsequence scan, and three-way partition.

Quick Sights

• Typical Time Complexity: O(n) after any required sorting; O(n log n) when sorting is part of the solution.
• Typical Space Complexity: O(1) extra space, excluding output.
• Core Mechanism: Maintain an invariant about the settled region and the unknown region. Move the pointer that is blocking progress, and explain exactly what candidates that movement discards.

Concept Explanation

Think of the input as a corridor. One pointer marks what is already settled; the other pointer explores or squeezes the unknown region. For sorted sums, the current sum tells you whether to increase the left side or decrease the right side. For palindrome and container problems, both ends move inward. For in-place partition problems, a write pointer marks the next correct slot while a read pointer scans.

A strong interview explanation always includes the discard rule: after this pointer moves, which candidates are impossible, and why?

Diagram

Recognition Cues

Look for this pattern when the prompt mentions sorted arrays, target sums, palindromes, subsequences, in-place movement, removing values, partitioning values, or maximizing/minimizing a candidate formed by two boundaries.

Problem List

Start with 125. Valid Palindrome, 167. Two Sum II, 283. Move Zeroes, and 075. Sort Colors. Then move to 015. 3Sum, 018. 4Sum, and 042. Trapping Rain Water.