Two Pointers: Pattern Intuition Guide¶
"Two points of attention, moving in coordinated rhythm β each step permanently narrows the world of possibilities."
The Situation That Calls for Two Pointers¶
Imagine you're standing at the edge of a long corridor with doors on both sides. You know the answer lies somewhere in this corridor, but checking every possible pair of doors would take forever.
Then you realize: you don't need to check everything. You can place one hand on the leftmost door and one on the rightmost door. Based on what you find, you know which hand to move. With each movement, doors behind you become irrelevant β forever excluded from consideration.
This is the essence of Two Pointers.
You encounter this pattern whenever: - You're working with a sorted or ordered sequence - You need to find pairs, tuples, or regions with certain properties - The relationship between elements is monotonic β changing one pointer predictably affects the outcome - You can eliminate possibilities based on the current state
The key insight: You're not searching β you're eliminating. Every pointer movement permanently shrinks the problem.
The Invariant: The Space Between¶
Every two pointers algorithm maintains a sacred region β the space where the answer must exist.
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β β
β [excluded] β left βββββββ answer space βββββββ right β [excluded] β
β β
β Once excluded, never reconsidered. β
β The region between pointers is the ONLY remaining hope. β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
The invariant says: If a valid answer exists, it lies within the current boundaries. Moving a pointer is a declaration: "I've proven that nothing behind this pointer can be part of the answer."
This is what makes two pointers work: each movement is a proof of exclusion. You're not guessing β you're eliminating with certainty.
The Irreversible Decision¶
Here's the crucial insight that separates two pointers from brute force:
Once a pointer moves, it never moves back.
When you advance left from position 3 to position 4, you've permanently decided: "No valid answer involves position 3 as the left element." This decision is irreversible.
This one-directional march is what transforms O(nΒ²) into O(n). Instead of checking all nΒ² pairs, each of the 2n pointer positions is visited at most once.
The irreversibility creates efficiency: you burn bridges as you cross them.
The Six Shapes of Two Pointers¶
Two pointer problems come in six distinct flavors. Recognizing the shape tells you exactly how to position and move the pointers.
Shape 1: Opposite Approach β "Closing the Gap"¶
The situation: Two sentinels stand at opposite ends of a corridor. They walk toward each other, meeting somewhere in the middle.
What it feels like: You're squeezing from both ends. The search space shrinks from the outside in.
The mental model:
Initial: L βββββββββββββββββββββββββββββββββββ R
β β
Step 1: L βββββββββββββββββββββββββββββ R
β
Step 2: L βββββββββββββββββββββββββ R
β
Step 3: L βββββββββββββββββββ R
...
Final: L R (or L crosses R)
The decision rule: Based on the current pair's property: - If the combined value is too small β move left right (seek larger) - If the combined value is too large β move right left (seek smaller) - If it matches β record and continue (or return immediately)
Why it works: Sorted order creates monotonicity. Moving left right can only increase its contribution. Moving right left can only decrease its contribution. This gives you precise control.
Classic problems: Two Sum II, Container With Most Water, 3Sum
Shape 2: Same Direction β "The Writer Following the Reader"¶
The situation: Two people walk the same corridor. One is a Reader who examines every door. The other is a Writer who only records the doors worth keeping.
What it feels like: You're filtering in-place. The Reader advances relentlessly; the Writer only moves when something passes the test.
The mental model:
Initial: [a] [b] [c] [d] [e] [f]
W R
β
Reader examines 'a'
'a' passes β Writer takes it, both advance
Step 2: [a] [b] [c] [d] [e] [f]
W R
β
Reader examines 'b'
'b' fails β only Reader advances
Step 3: [a] [b] [c] [d] [e] [f]
W R
β
Reader examines 'c'
'c' passes β Writer takes it, both advance
Final: [a] [c] [x] [x] [x] [x]
β
New logical end (write position)
The decision rule: - Reader always advances - Writer only advances when the current element should be kept - Elements are copied from Reader position to Writer position
Why it works: The Writer index marks the boundary of "good" elements. Everything before Writer is the output; everything at or after is either unprocessed or discarded.
The invariant: arr[0:write] contains exactly the valid elements seen so far, in their original order.
Classic problems: Remove Duplicates, Remove Element, Move Zeroes
Shape 3: Fast and Slow β "The Tortoise and the Hare"¶
The situation: Two runners on a track. One runs twice as fast as the other. If the track is a loop, the fast runner will eventually lap the slow one.
What it feels like: You're detecting a cycle by observing when speeds converge.
The mental model:
Linear track (no cycle):
Slow: 1 step per turn
Fast: 2 steps per turn
Fast reaches the end first β No cycle
Circular track (cycle exists):
βββββββββββββββββββββββββββββ
β β
β β
[A] β [B] β [C] β [D] β [E] ββ
S F
Fast enters cycle first
Slow eventually enters
Fast "chases" slow from behind
Gap closes by 1 each step
They MUST meet inside the cycle
The decision rule: - Slow moves 1 step - Fast moves 2 steps - If they meet β cycle exists - If Fast reaches null β no cycle
Why it works: If there's a cycle, once both pointers are inside, the relative distance changes by 1 each iteration. Since the cycle length is finite, they must eventually collide.
Finding the cycle start (Phase 2): - When they meet, reset Slow to head - Move both at speed 1 - They meet again at the cycle start
This works because of the mathematical relationship between the meeting point and the cycle entry.
Classic problems: Linked List Cycle, Happy Number, Find Duplicate Number
Shape 4: Partitioning β "The Bouncer Sorting the Queue"¶
The situation: A bouncer at a club entrance directs each person to one of three sections: left, middle, or right. Each person is examined once and placed in their final position.
What it feels like: You're sorting without sorting β classifying elements into regions in a single pass.
The mental model (Dutch National Flag):
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β β
β [ < pivot ] [ = pivot ] [ unclassified ] [ > pivot ] β
β βββββββββββββ βββββββββββββ ββββββββββββββββββ βββββββββββ β
β 0 low-1 low mid-1 mid high high+1 n-1β
β β β
β examine this β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Three pointers, three regions: - low: boundary between "less than" and "equal to" - mid: the examiner, scanning the unclassified region - high: boundary between "unclassified" and "greater than"
The decision rule: - If arr[mid] < pivot: swap with low, advance both low and mid - If arr[mid] > pivot: swap with high, retreat high only (the swapped element needs examination) - If arr[mid] == pivot: advance mid only
Why it works: Each element is placed in its final region. The mid pointer only advances when we're certain the element at mid belongs to the middle or has been swapped from a known region.
Classic problems: Sort Colors, Partition Array, Sort By Parity
Shape 5: Dedup Enumeration β "Pinning Down the Triangle"¶
The situation: You need to find all unique triplets (or quadruplets) with a target property. You've seen Two Sum with a hash map β now imagine finding all Two Sum pairs, without duplicates, inside a loop.
What it feels like: You pin down one corner, then use opposite pointers to sweep the remaining candidates.
The mental model:
Find all triplets summing to 0:
For each i (the anchor):
βββββββββββββββββββββββββββββββββββββββββββββββββββ
β nums[i] is FIXED for this iteration β
β β
β [anchor] [left βββββββββββββββββββ right] β
β i i+1 n-1 β
β β
β Use opposite pointers to find pairs β
β that complete the triplet β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββ
The deduplication insight: After sorting: - Skip i if nums[i] == nums[i-1] (don't anchor at duplicate) - After finding a triplet, skip left forward while nums[left] == nums[left+1] - After finding a triplet, skip right backward while nums[right] == nums[right-1]
Why it works: Sorting enables two things: 1. The opposite-pointer technique for finding pairs in O(n) 2. Adjacent duplicates can be skipped to avoid duplicate triplets
The irreversible truth: Once anchor i is processed, all triplets starting with nums[i] are found. Moving to i+1 permanently excludes nums[i] from being an anchor again.
Classic problems: 3Sum, 4Sum, 3Sum Closest
Shape 6: Merge β "Two Rivers Joining"¶
The situation: Two sorted streams need to become one. You hold a cup at the head of each stream. You pour from whichever cup has the smaller value.
What it feels like: You're interleaving two sorted sequences into a single sorted sequence.
The mental model:
Stream 1: [1] [3] [5] [7]
β
i
Stream 2: [2] [4] [6]
β
j
Output: [1]
βββ smaller of arr1[i] and arr2[j]
After pouring 1:
Stream 1: [1] [3] [5] [7]
β
i
Output: [1] [2]
βββ now arr2[j] is smaller
The decision rule: - Compare arr1[i] and arr2[j] - Take the smaller one, advance that pointer - When one stream empties, pour the remainder of the other
Why it works: Both streams are sorted. The smallest unpoured element must be at one of the two heads. By always taking the smaller head, we maintain sorted order in the output.
In-place variant (LeetCode 88): Write from the end to avoid overwriting unprocessed elements.
Classic problems: Merge Sorted Array, Merge Two Sorted Lists, Squares of Sorted Array
Pattern Recognition: "Is This a Two Pointers Problem?"¶
Ask yourself these questions:
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β β
β 1. Is the sequence SORTED (or can I sort it)? β
β βββ No? β Two pointers unlikely (consider hash map) β
β β
β 2. Am I looking for PAIRS or TUPLES with a property? β
β βββ Yes? β Opposite pointers or dedup enumeration β
β β
β 3. Do I need to modify the array IN-PLACE? β
β βββ Yes? β Same-direction (writer pattern) β
β β
β 4. Am I detecting a CYCLE in a sequence? β
β βββ Yes? β Fast-slow pointers β
β β
β 5. Am I PARTITIONING by some property? β
β βββ Yes? β Dutch flag pattern β
β β
β 6. Am I MERGING two sorted sequences? β
β βββ Yes? β Merge pattern β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
The Moment of Recognition¶
You're reading a problem. You notice:
- "Given a sorted array..." β Sorting enables deterministic pointer movement
- "Find two elements that sum to..." β Pair search screams opposite pointers
- "Remove ... in-place with O(1) extra space" β Same-direction writer
- "Detect if there's a cycle..." β Fast-slow pointers
- "Sort the array so that all X come before Y..." β Partitioning
- "Merge two sorted..." β Merge pattern
And you feel it: This is a two pointers problem. I know exactly which shape.
That's the goal. Instant recognition. No hesitation.
Why O(n)? The Amortized Argument¶
Every two pointers algorithm achieves O(n) through the same principle:
Each pointer only moves forward.
Consider opposite pointers: - left starts at 0, can only increase, ends at most at n-1: at most n moves - right starts at n-1, can only decrease, ends at most at 0: at most n moves - Total moves: at most 2n = O(n)
Consider same-direction: - read visits each position exactly once: n moves - write moves at most once per read move: at most n moves - Total moves: at most 2n = O(n)
The magic: No element is ever reconsidered. This is the irreversibility that transforms quadratic brute force into linear elegance.
Visual Intuition: The Six Shapes Side by Side¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β OPPOSITE POINTERS β
β L β β β β β β β β β β β β β β β β β β β β β β R β
β Closing in from both ends β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β SAME DIRECTION (WRITER) β
β W β β β β β (selective) β
β R β β β β β β β β β β (relentless) β
β Writer follows reader, keeping only what passes β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β FAST-SLOW β
β S β β β β β β β β
β F β β β β β β β β β β β β β β β
β If they meet, there's a cycle β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β PARTITIONING (DUTCH FLAG) β
β [ < ] [ = ] [ ? ] [ > ] β
β low mid high β
β Three regions, one-pass classification β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β DEDUP ENUMERATION β
β [anchor] L β β β β β β β β β β β β β β β R β
β i opposite pointers in subarray β
β Fix one, sweep the rest β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β MERGE β
β [1] [3] [5] β β
β [2] [4] [6] β ββ> [1] [2] [3] [4] [5] [6] β
β Two sorted streams becoming one β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Detailed Traces: Seeing the Pattern in Motion¶
Trace 1: Opposite Pointers β Two Sum II¶
Problem: Find two numbers in sorted array that sum to target.
Input: nums = [2, 7, 11, 15], target = 9
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Step 0: [2] [7] [11] [15] target = 9 β
β L R sum = 2 + 15 = 17 β
β 17 > 9 β move R left β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β Step 1: [2] [7] [11] [15] β
β L R sum = 2 + 11 = 13 β
β 13 > 9 β move R left β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β Step 2: [2] [7] [11] [15] β
β L R sum = 2 + 7 = 9 β
β 9 == 9 β FOUND! Return [1, 2] β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Key observations:
β’ We never examined (2,11) or (7,11) or (7,15) β they were eliminated!
β’ Each step provably excluded possibilities based on monotonicity.
Trace 2: Same-Direction β Remove Duplicates¶
Problem: Remove duplicates from sorted array in-place.
Input: nums = [1, 1, 2, 2, 2, 3]
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Initial: [1] [1] [2] [2] [2] [3] β
β W R β
β β
β Step 0: nums[R]=1, nums[W-1]=undefined β KEEP β
β write_index becomes 1 β
β [1] [1] [2] [2] [2] [3] β
β W R β
β β
β Step 1: nums[R]=1 == nums[W-1]=1 β SKIP β
β [1] [1] [2] [2] [2] [3] β
β W R β
β β
β Step 2: nums[R]=2 != nums[W-1]=1 β KEEP β
β [1] [2] [2] [2] [2] [3] β
β W R β
β β
β Step 3: nums[R]=2 == nums[W-1]=2 β SKIP β
β [1] [2] [2] [2] [2] [3] β
β W R β
β β
β Step 4: nums[R]=2 == nums[W-1]=2 β SKIP β
β [1] [2] [2] [2] [2] [3] β
β W R β
β β
β Step 5: nums[R]=3 != nums[W-1]=2 β KEEP β
β [1] [2] [3] [2] [2] [3] β
β W R (done) β
β β
β Result: First 3 elements [1, 2, 3] are the unique values β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Invariant maintained throughout:
β’ nums[0:W] contains exactly the unique elements seen so far
β’ Elements are in their original sorted order
Trace 3: Fast-Slow β Cycle Detection¶
Problem: Detect if linked list has a cycle.
Input: 1 β 2 β 3 β 4 β 5 β 3 (cycle back to node 3)
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β The linked list: β
β β
β 1 β 2 β 3 β 4 β 5 β
β β β β
β βββββββββ β
β β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β Step 0: S=1, F=1 (start) β
β β
β Step 1: S=2 (moved 1) β
β F=3 (moved 2) β
β β
β Step 2: S=3 (moved 1) β
β F=5 (moved 2) β
β β
β Step 3: S=4 (moved 1) β
β F=4 (moved 2: 5β3β4) β F wrapped around the cycle! β
β β
β Step 4: S=5 (moved 1) β
β F=3 (moved 2: 4β5β3) β
β β
β Step 5: S=3 (moved 1: 5β3) β
β F=5 (moved 2: 3β4β5) β
β β
β Step 6: S=4 (moved 1) β
β F=4 (moved 2: 5β3β4) β
β β
β S == F β CYCLE DETECTED! β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Why they MUST meet:
β’ Once both are in the cycle, Fast "chases" Slow
β’ The gap closes by 1 each step (Fast gains 1 on Slow)
β’ Maximum steps until collision = cycle length
Trace 4: Dutch National Flag β Sort Colors¶
Problem: Sort array containing only 0s, 1s, and 2s.
Input: nums = [2, 0, 2, 1, 1, 0]
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Legend: low (L), mid (M), high (H) β
β Regions: [0..L) = 0s, [L..M) = 1s, [M..H] = unclassified, (H..] = 2s β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β Initial: [2] [0] [2] [1] [1] [0] β
β L,M H β
β β examine 2: >1 β swap with H, H-- β
β β
β Step 1: [0] [0] [2] [1] [1] [2] β
β L,M H β
β β examine 0: <1 β swap with L, L++, M++ β
β β
β Step 2: [0] [0] [2] [1] [1] [2] β
β L,M H β
β β examine 0: <1 β swap with L (self), L++, M++ β
β β
β Step 3: [0] [0] [2] [1] [1] [2] β
β L,M H β
β β examine 2: >1 β swap with H, H-- β
β β
β Step 4: [0] [0] [1] [1] [2] [2] β
β L,M H β
β β examine 1: =1 β M++ β
β β
β Step 5: [0] [0] [1] [1] [2] [2] β
β L M,H β
β β examine 1: =1 β M++ β
β β
β Step 6: [0] [0] [1] [1] [2] [2] β
β L M (M > H, done!) β
β H β
β β
β Result: [0, 0, 1, 1, 2, 2] β sorted in single pass! β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Key insight:
β’ When swapping with high, we DON'T advance mid β the swapped element is unclassified
β’ When swapping with low, we DO advance mid β the swapped element is known to be 0 or 1
From Intuition to Implementation¶
Only now β after the patterns feel inevitable β does code become useful.
Opposite Pointers Template¶
def opposite_pointers(arr):
"""
Two pointers approaching from opposite ends.
Use when: sorted array, finding pairs with target property.
"""
left, right = 0, len(arr) - 1
while left < right:
current = evaluate(arr, left, right)
if current == target:
return record_answer(left, right)
elif current < target:
left += 1 # Need larger: move left forward
else:
right -= 1 # Need smaller: move right backward
return no_answer_found
Same-Direction (Writer) Template¶
def same_direction(arr):
"""
Writer follows reader, keeping valid elements.
Use when: in-place modification, filtering, deduplication.
"""
write = 0
for read in range(len(arr)):
if should_keep(arr, read, write):
arr[write] = arr[read]
write += 1
return write # New logical length
Fast-Slow Template¶
def fast_slow(head):
"""
Detect cycle using speed differential.
Use when: cycle detection, finding midpoint.
"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True # Cycle detected
return False # No cycle
Dutch National Flag Template¶
def partition_three_way(arr, pivot=1):
"""
Partition into three regions in single pass.
Use when: sorting by category, three-way partition.
"""
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] < pivot:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] > pivot:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1 # Don't advance mid β swapped element is unknown
else:
mid += 1
Merge Template¶
def merge_sorted(arr1, arr2):
"""
Merge two sorted arrays into one.
Use when: combining sorted sequences.
"""
i, j = 0, 0
result = []
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
Quick Reference: Shape Selection Guide¶
| When You See... | Think... | Shape |
|---|---|---|
| "Sorted array, find pair with sum X" | Closing the gap | Opposite |
| "Remove/modify in-place with O(1) space" | Writer follows reader | Same-Direction |
| "Detect cycle in linked list" | Tortoise and hare | Fast-Slow |
| "Sort array with only 2-3 distinct values" | Bouncer sorting queue | Partitioning |
| "Find all unique triplets summing to X" | Pin one, sweep the rest | Dedup Enumeration |
| "Merge two sorted arrays" | Two rivers joining | Merge |
Common Pitfalls¶
Pitfall 1: Forgetting the Sorted Prerequisite¶
Two pointers works because sorting creates monotonicity. If you need two pointers but the array isn't sorted, sort it first (if allowed).
Pitfall 2: Off-by-One in Termination¶
- Opposite:
while left < right(not<=) for pair problems - Same-direction:
for read in range(len(arr))visits all elements - Fast-slow: check
fast and fast.nextbefore advancing
Pitfall 3: Not Handling Duplicates in Enumeration¶
For 3Sum and similar, always skip duplicates at both the anchor level and the pointer level:
Pitfall 4: Advancing Mid in Dutch Flag After High Swap¶
When you swap arr[mid] with arr[high], the new value at mid is unclassified. Don't advance mid β examine it in the next iteration.
The Two Pointers Mantra¶
One invariant: the answer lies between.
One rule: once passed, never reconsidered.
One result: O(n) elegance from O(nΒ²) brute force.
When you see sorted sequences and pair-finding, think of the sentinels. When you see in-place modification, think of the writer following the reader. When you see cycles, think of the tortoise and hare.
The pattern is always the same: coordinated movement, irreversible exclusion, linear time.
For implementation templates and problem mappings, see templates.md.