When to Use Two Pointers
Two pointers reduce O(n²) brute force to O(n) or O(n log n) by exploiting sorted order or the monotonic nature of the search space. Recognize the pattern: “find a pair/triple/subarray with a target property” on a sorted array, or “longest/shortest window with a constraint.”
Opposite-End Two Pointers
Left pointer starts at index 0, right starts at end. Move them toward each other based on the comparison result. Works when the array is sorted or when there’s a clear invariant about moving each pointer.
# Two Sum II - sorted array (LC 167)
def twoSum(numbers, target):
l, r = 0, len(numbers) - 1
while l < r:
s = numbers[l] + numbers[r]
if s == target: return [l+1, r+1]
elif s < target: l += 1
else: r -= 1
# Container With Most Water (LC 11)
def maxArea(height):
l, r = 0, len(height) - 1
result = 0
while l < r:
result = max(result, min(height[l], height[r]) * (r - l))
if height[l] < height[r]: l += 1
else: r -= 1
return result
Three Sum (LC 15)
Fix one element, then use two pointers on the remainder. Sort first (O(n log n)), then for each element at index i, run two-pointer on nums[i+1..n-1]. Skip duplicates at each level.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dup
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
result.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
elif s < 0: l += 1
else: r -= 1
return result
Sliding Window (Same-Direction Two Pointers)
Both pointers move in the same direction. Left pointer is the window start; right expands the window. Shrink from left when the window violates the constraint.
# Minimum Window Substring (LC 76)
from collections import Counter
def minWindow(s, t):
need = Counter(t)
missing = len(t)
best = ""
l = 0
for r, c in enumerate(s):
if need[c] > 0: missing -= 1
need[c] -= 1
if missing == 0:
while need[s[l]] < 0:
need[s[l]] += 1
l += 1
if not best or r - l + 1 < len(best):
best = s[l:r+1]
need[s[l]] += 1
missing += 1
l += 1
return best
Longest Substring Without Repeating Characters (LC 3)
def lengthOfLongestSubstring(s):
char_idx = {}
l = result = 0
for r, c in enumerate(s):
if c in char_idx and char_idx[c] >= l:
l = char_idx[c] + 1
char_idx[c] = r
result = max(result, r - l + 1)
return result
Jump l directly to char_idx[c]+1 rather than incrementing one at a time — O(n) not O(n²).
Trapping Rain Water (LC 42)
def trap(height):
l, r = 0, len(height) - 1
left_max = right_max = 0
water = 0
while l < r:
if height[l] = left_max: left_max = height[l]
else: water += left_max - height[l]
l += 1
else:
if height[r] >= right_max: right_max = height[r]
else: water += right_max - height[r]
r -= 1
return water
Two Pointers on Two Arrays (Merge Step)
Merge two sorted arrays, find intersection (LC 349/350), find the smallest range covering elements from k lists (LC 632 — use heap for k lists). For two arrays: advance the pointer in the smaller-value array.
Key Decision Points
- Opposite-end pointers: sorted array, target sum, or monotonic property allows one pointer to advance
- Same-direction (sliding window): subarray/substring with constraint, window size grows and shrinks
- Fast/slow pointers: cycle detection, finding middle of linked list, nth-from-end
- Two arrays: merge step, intersection, smallest range
Meta coding interviews frequently test two pointers and sliding window patterns. See common questions for Meta interview: two pointers and sliding window problems.
Google coding interviews test two pointers patterns. See problems for Google interview: two pointers and array problems.
Amazon coding interviews test two pointers and sliding window. Review patterns for Amazon interview: two pointers and subarray problems.