2.2 Two Pointers

Deep Dive: Why Moving Pointers Eliminates Candidates

Beginner tip: Two pointers is like two people walking toward each other from opposite ends of a bridge. At each step, you decide who should step forward based on what you are looking for. This lets you check all pairs of positions in one pass (O(n)) instead of checking every combination (O(n^2)).

Container With Most Water -- Pointer Logic Visualized

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

L=0  R=8  area = min(1,7)*8 = 8     height[L]=1 is shorter -> move L
L=1  R=8  area = min(8,7)*7 = 49    height[R]=7 is shorter -> move R
L=1  R=7  area = min(8,3)*6 = 18    height[R]=3 is shorter -> move R
L=1  R=6  area = min(8,8)*5 = 40    equal -> move either
...
Best = 49

Why moving the shorter side is optimal: The area is limited by the shorter line. Moving the taller side can only make the container narrower AND keep the same height limit. It can NEVER improve. Moving the shorter side MIGHT find a taller line.

Remove Duplicates -- Read/Write Pointer

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

write=1  read=1  nums[1]=0 == nums[0]=0  -> skip
write=1  read=2  nums[2]=1 != nums[0]=0  -> nums[1]=1, write=2
write=2  read=3  nums[3]=1 == nums[1]=1  -> skip
write=2  read=4  nums[4]=1 == nums[1]=1  -> skip
write=2  read=5  nums[5]=2 != nums[1]=1  -> nums[2]=2, write=3
...
Result: [0, 1, 2, 3, 4, ...] length = 5

Read pointer scans everything. Write pointer only advances when new unique value found. Everything before write is the clean result.

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Two Pointers

Why It Works

Brute force: Check all pairs = O(n^2). Two pointers on sorted data: Eliminate pairs intelligently = O(n).

The Core Insight

If the array is sorted and arr[L] + arr[R] is too big, decreasing R makes it smaller. If too small, increasing L makes it bigger. You never need to check all pairs.

The Four Variants

TYPE 1: OPPOSITE DIRECTION (most common)
  L starts at 0, R starts at end. Converge inward.
  Use for: Two Sum (sorted), Container With Most Water, Valid Palindrome

TYPE 2: SAME DIRECTION (fast/slow)
  Both start at 0. Fast moves ahead, slow follows.
  Use for: Remove duplicates, Move Zeroes, partition

TYPE 3: FAST & SLOW (different speeds)
  Slow moves 1 step, Fast moves 2 steps.
  Use for: Cycle detection, find middle of linked list

TYPE 4: MERGE (two separate arrays)
  One pointer per array, advance the smaller.
  Use for: Merge two sorted arrays/lists

When You See a Problem, Ask Yourself

1. Is input sorted (or can I sort it)? -> Opposite direction pointers
2. "Find pair/triplet with target sum"? -> Sort + two pointers
3. "Remove/partition in place"? -> Same direction (read/write pointers)
4. "Cycle in linked list"? -> Fast & slow
5. "Is it a palindrome"? -> Opposite direction from both ends

The 3Sum Recipe (Most Asked)

1. Sort the array
2. For each element arr[i] (the first number):
   a. Set L = i+1, R = end
   b. Two-pointer search for target - arr[i]
   c. Skip duplicates for i, L, and R

Common Mistakes

• Using two pointers on UNSORTED data (doesn't work for sum problems)
• Not skipping duplicates in 3Sum -> duplicate triplets
• Moving the wrong pointer (think: which direction makes the sum bigger/smaller?)

Problems

#	Problem	Variant	Status
1	Two Sum II (sorted)	Opposite	[ ]
2	3Sum	Sort + Opposite	[ ]
3	Container With Most Water	Opposite	[ ]
4	Trapping Rain Water	Opposite	[ ]
5	Remove Duplicates from Sorted Array	Same direction	[ ]
6	Move Zeroes	Same direction	[ ]
7	Linked List Cycle	Fast & Slow	[ ]
8	Valid Palindrome	Opposite	[ ]

Notes