roadmap/Two Pointers

Topic 2 / 16

Two Pointers

BeginnerFoundation~3 days
Easy to grasp
progress0 / 10 solved

Eliminate nested loops by moving pointers inward or outward based on a condition.

Concept

Place two pointers at different positions in an array or string and move them toward each other (or apart) based on a condition. This eliminates the inner loop of O(n²) brute-force solutions. Requires sorted input in most cases — if unsorted, sort first.

When to use this pattern
  • ◆Sorted array with target pair sum
  • ◆Palindrome checking
  • ◆Remove duplicates in-place
  • ◆Trapping water or container problems
  • ◆Merging two sorted arrays
Common patterns
Converging pointers
Left at 0, right at n-1. Move inward based on sum vs target.
Same-direction pointers
Slow pointer tracks valid position; fast pointer scans ahead.
Merge pattern
Two pointers across two separate arrays, advance the smaller one.
Visual walkthrough
Two pointers — sorted array, target sum = 7
-4
lo
-1
1
0
2
0
3
1
4
2
5
3
6
5
7
8
hi
Sum 4 < 7 → move lo right
step 1 / 2
Brute force → optimal thinking
Brute force
Check every pair (i, j) → O(n²).
Observation
If the array is sorted, a too-small sum means move left pointer right; too-large means move right pointer left.
Optimization
Start pointers at both ends. Each step eliminates one possibility — O(n) total moves.
Final complexity
O(n log n) if sorting needed, O(n) if already sorted. O(1) extra space.
Quick Recall Check

What must usually be true before applying converging two pointers?

In 3Sum, why do we skip duplicate values of the outer index?

Which pointer do you move when the sum is too large in a sorted two-pointer search?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Arrays & Hashing
next
Sliding Window
→
Progress is saved on this device