When to Use Two Pointers?

Core Idea: Maintain two positions in data structure and move them based on conditions. Avoids nested loops (O(n²) → O(n)).

Pattern Recognition:

Movement Strategies:

Convergent: Start at both ends (i=0, j=n-1), move inward based on condition.

Same Direction: Both move left-to-right at different speeds (sliding window).

Why It Works: Each pointer moves at most n times = O(n) total. Compare this to brute force checking all pairs = O(n²).

Valid Palindrome

O(n) Time / O(1) Space

Goal: Check if string is palindrome (ignoring non-alphanumeric, case-insensitive).

Technique: Convergent Two Pointers

Why Two Pointers? Palindrome = symmetric. Compare first with last, second with second-last, etc. Two pointers naturally express this symmetry. Alternative (reverse string) uses O(n) space; this uses O(1).

Key Insight: Skip invalid characters while maintaining pointer positions. Inner loops advance past non-alphanumeric before comparing. Only move to next comparison when both pointers point to valid chars.

i, j := 0, len(s)-1 for i < j: while i

Trap:

Check `i < j` in skip loops to avoid index errors.

Two Integer Sum II

O(n) Time / O(1) Space

Goal: Find two numbers in sorted array that sum to target.

Technique: Convergent Search

Why Two Pointers? Array is sorted—this is the key! If sum too small, need bigger number (move left pointer right). If sum too large, need smaller number (move right pointer left). Hash map works but uses O(n) space; problem demands O(1).

Key Insight: Sorted array gives direction. Each comparison eliminates one possibility. Pointers always converge because we're monotonically narrowing search space. Can't miss the answer.

l, r := 0, len(nums)-1 while l < r: sum := nums[l] + nums[r] if sum < target: l++ else if sum > target: r-- else: return [l+1, r+1] // 1-indexed

Sorted Required:

Won't work on unsorted array. Sort first if needed.

3Sum

O(n²) Time / O(1) Space

Goal: Find all unique triplets that sum to zero.

Technique: Fixed + Two Pointers

Why This Approach? Brute force is O(n³) checking all triplets. Instead, fix first element, then use two pointers for remaining two (O(n) for each fixed element = O(n²) total). Must sort first to enable two pointer technique and skip duplicates efficiently.

Key Insight: After sorting, fix `i`, search for `j,k` where `nums[i]+nums[j]+nums[k]=0`. This reduces 3Sum to many 2Sum problems. Dedup by skipping consecutive equal values at all three positions.

  1. Sort array O(n log n).
  2. For each `i`: set `j=i+1`, `k=n-1`.
  3. Use two pointers: if sum<0, j++; if sum>0, k--; if sum=0, save & skip dupes.
  4. Skip duplicates: while `nums[i]==nums[i-1]` continue.
sort(nums) for i in 0..n: if i>0 && nums[i]==nums[i-1]: continue j, k := i+1, n-1 while j < k: sum := nums[i]+nums[j]+nums[k] if sum<0: j++ else if sum>0: k-- else: res.add([nums[i],nums[j],nums[k]]) j++; while j

Dedup Critical:

Must skip duplicates at all 3 positions to avoid duplicate triplets.

Container With Most Water

O(n) Time / O(1) Space

Goal: Find two bars that form container with max water area.

Technique: Greedy Two Pointers

Why Greedy Works? Area = min(h[i], h[j]) × (j - i). Start with max width (i=0, j=n-1). To improve area, we need taller bars. Moving the taller pointer only decreases width without potential height gain. Moving shorter pointer might find taller bar. This greedy choice is optimal.

Key Insight: We never miss optimal solution. When we move shorter pointer, we're abandoning all pairs with current pointer (proven to be suboptimal due to width decrease). Each step eliminates possibilities that can't be better.

i, j := 0, n-1 maxArea := 0 while i < j: area := min(h[i], h[j]) * (j - i) maxArea = max(maxArea, area) if h[i] < h[j]: i++ else: j--

Proof Sketch: If h[i]

Trapping Rain Water

O(n) Time / O(1) Space

Goal: Calculate water trapped between elevation bars.

Technique: Two Pointers + Max Tracking

Why This Works? Water at position i = min(leftMax, rightMax) - h[i]. Brute force: for each position, scan left and right for max (O(n²)). Precompute arrays: O(n) time but O(n) space. Two pointers: track maxes while moving, O(1) space!

Key Insight: Water level determined by shorter wall. If leftMax < rightMax, we KNOW water at left pointer is limited by leftMax (rightMax is guaranteed higher). Process left side. Vice versa for right. Only need to track which side is limiting factor.

l, r := 0, n-1 leftMax, rightMax := h[l], h[r] water := 0 while l < r: if leftMax < rightMax: l++ leftMax = max(leftMax, h[l]) water += leftMax - h[l] else: r-- rightMax = max(rightMax, h[r]) water += rightMax - h[r]

Subtle Point: We don't need exact max on both sides, just need to know which side is limiting. The smaller of leftMax/rightMax determines water level.

Two Pointer Patterns Summary

1. Convergent (Opposite Ends):

Use When: Sorted array, palindrome check, optimization with width×height.

Examples: Two Sum II, Valid Palindrome, Container With Most Water.

Template: `l=0, r=n-1; while l

2. Fixed + Two Pointers:

Use When: Finding k-tuples (triplets, quadruplets) that satisfy condition.

Examples: 3Sum, 4Sum.

Template: `for i: {l=i+1, r=n-1; two pointer search}`

3. Greedy Pointer Movement:

Use When: Optimization problem where one pointer choice is clearly better.

Examples: Container With Most Water (move shorter bar).

Key: Prove moving one pointer can't miss optimal solution.

4. State Tracking Pointers:

Use When: Need to maintain running state (max, min, sum) while traversing.

Examples: Trapping Rain Water (track leftMax/rightMax).

Key: Update state variables as pointers move.

Common Thread:

All avoid O(n²) by intelligently eliminating impossible solutions as pointers move. Each pointer moves at most n times = O(n) total operations.