-
Notifications
You must be signed in to change notification settings - Fork 0
014 — Two Pointers
This is the first chapter in the Patterns section — and the shift in mindset starts here. Data structure chapters answered "how do I store this?" Pattern chapters answer "given a stored thing, what's the reusable shape of the algorithm that solves it?" Two Pointers is often the first pattern people learn, and it's the one that teaches the core skill of pattern recognition: noticing that a brute-force O(n²) nested loop can collapse into a single O(n) pass by walking two positions through the data at once, instead of restarting an inner loop from scratch every time.
Picture two people at opposite ends of a long hallway lined with lockers, each checking whether a pair of lockers meets some condition — say, their combined contents weigh exactly what a shipping label demands. Instead of one person walking the entire hallway for every single locker at the other end (that's the brute-force nested loop), both people start at the far ends and walk toward each other. Every time they meet at a pair, they check the condition, and each person decides — based on that check — whether they need to step inward, or whether their partner does. They never backtrack. They never re-check a pair either of them has already ruled out. The hallway gets covered exactly once, from both directions at once.
That's the whole idea: two positions ("pointers") moving through the same data, each only ever advancing, never revisiting ground already covered.
Two Pointers is a strong reach when you see:
- A sorted array (or one you can sort) combined with a phrase like "find a pair/triplet that sums to X" or "find two numbers such that..." — sortedness is what lets each pointer's movement be a meaningful, one-directional decision (move left in if the sum's too small, move right in if too big).
- "Palindrome" checks, or anything comparing an array/string against its own reverse — one pointer from the front, one from the back, walking inward.
- Two separate sorted sequences that need to be merged or compared ("merge two sorted lists/arrays", "find the intersection of two sorted arrays") — one pointer per sequence, both walking forward together.
- "Container" / "area between two lines" / "maximum width" problems where you're choosing two indices and want to optimize something about the span between them — classic converging-pointers-from-both-ends shape.
The unifying tell: you're choosing two indices into a linear structure, and there's some monotonic property (sortedness, or a value that only grows/shrinks as a pointer moves) that lets you rule out a whole range of candidates with a single comparison, instead of checking every pair.
Two pointers converging from both ends of a sorted array, hunting for a pair that sums to 10:
index: 0 1 2 3 4 5
array: [ 1, 3, 4, 6, 8, 9 ]
▲ ▲
left(l) right(r)
step 1: 1 + 9 = 10 → target found immediately!
--- if the target were 12 instead ---
step 1: arr[l] + arr[r] = 1 + 9 = 10 → too small → l moves right
step 2: arr[l] + arr[r] = 3 + 9 = 12 → found!
--- if the sum is too BIG, r moves left instead ---
(too small → advance l | too big → retreat r)
Each step eliminates an entire row/column of the (l, r) grid —
that's the O(n²) → O(n) collapse: every wrong answer rules out
every other pair that shares the "losing" pointer's position.
func twoPointerTemplate(_ array: [Int], target: Int) -> (Int, Int)? {
var left = 0
var right = array.count - 1
while left < right {
// 🔧 Fill in: compute whatever "current" value the two pointers represent.
let current = array[left] + array[right]
if current == target {
return (left, right) // 🔧 Found — return/record the answer.
} else if current < target {
left += 1 // 🔧 Current is too small — grow it by moving left inward.
} else {
right -= 1 // 🔧 Current is too big — shrink it by moving right inward.
}
}
return nil // 🔧 No pair satisfied the condition.
}The skeleton never changes: two indices starting at opposite ends, a loop that runs while left < right, and per-iteration logic that always moves at least one pointer strictly inward based on a comparison — never both outward, never the same pointer twice without a comparison in between.
Container With Most Water — given an array height where height[i] is the height of a vertical line at index i, find two lines that, together with the x-axis, form a container holding the most water. The container's capacity is min(height[l], height[r]) * (r - l).
func maxArea(_ height: [Int]) -> Int {
var left = 0
var right = height.count - 1
var best = 0
while left < right {
let width = right - left
let currentArea = min(height[left], height[right]) * width
best = max(best, currentArea)
// The container's height is capped by the SHORTER line — so the only
// way a future pair could possibly beat this one is if it has a taller
// shorter-line. Moving the taller pointer inward can only shrink the
// width without any chance of raising the limiting height. So always
// advance the pointer at the shorter line.
if height[left] < height[right] {
left += 1
} else {
right -= 1
}
}
return best
}
// smoke test
print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])) // 49Mapped onto the template: left/right start at the array's ends exactly as in the skeleton. Instead of hunting for an exact target, the "current value" being tracked is the container's area, and best records the running maximum instead of returning on the first match. The pointer-movement decision — which pointer inward, and why it's safe to discard the other — is the one piece of reasoning that changes per problem; the loop shape around it never does.
Two Pointers is two people walking toward each other down a sorted hallway, each step ruling out everything behind them.
You're given a problem: "Given a sorted array of unique integers and a target, determine if there exist two numbers whose difference equals the target." Would you reach for Two Pointers here? If so, describe exactly how the pointer-movement rule would differ from the "sum to target" version above — and if not, explain what property is missing that Two Pointers depends on.
⬅️ Previous: Segment & Fenwick Trees · Next: Sliding Window ➡️