Two-Pointer Core Idea
Two pointers maintain two indices into a sorted or structured array, moving toward each other or in the same direction. The key insight: when the data has a monotonic property (sorted order, or a property that improves as you move one pointer in a direction), two pointers exploit that property to avoid examining every pair. O(n) instead of O(n^2). Two variants: opposite ends (left starts at 0, right at n-1 — move inward based on comparison). Same direction (fast and slow, or a fixed-size window variant). Prerequisite for opposite-end pointers: the array is sorted, or the property of interest changes monotonically as pointers move.
Pattern 1: Two Sum on Sorted Array (LC 167)
Two pointers on a sorted array: left=0, right=n-1. If nums[left]+nums[right] == target: found. If target: right–. O(n). Why it works: if the sum is too small, the smallest element can only be increased — move left forward. If too large, the largest can only be decreased — move right back. No pair is missed because: if (left, right) doesn’t work, the skipped pairs are definitely wrong (they would make the sum even more wrong in the same direction).
Pattern 2: Three Sum (LC 15)
Sort the array. Fix one element (index i), then use two pointers for the remaining pair. For each i: set left=i+1, right=n-1. Standard two-sum on the sorted suffix with target = -nums[i]. Skip duplicates: after finding a valid triplet, skip all equal values at left and right pointers. Skip duplicate values of i as well (to avoid duplicate triplets). O(n^2) total.
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dup
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return resultPattern 3: Trapping Rain Water (LC 42)
Two-pointer approach: the water at each position = min(max_height_left, max_height_right) – height[position]. Track left_max and right_max. Move the pointer on the side with the smaller max (because that side determines the water level). When height[left] = left_max, right can only help, not hurt). We can safely compute water at left.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] = left_max: left_max = height[left]
else: water += left_max - height[left]
left += 1
else:
if height[right] >= right_max: right_max = height[right]
else: water += right_max - height[right]
right -= 1
return waterPattern 4: Container With Most Water (LC 11)
Two pointers at both ends. Area = min(height[left], height[right]) * (right – left). Move the pointer with the smaller height inward (moving the taller pointer can only decrease or maintain width while the bottleneck — the shorter side — stays the same or worsens). O(n). Sort variant (LC 16 Three Sum Closest): same three-sum structure but track minimum absolute difference instead of exact match.
Pattern 5: Palindrome Verification and String Problems
LC 125 (Valid Palindrome): left and right pointers, skip non-alphanumeric, compare case-insensitively. LC 680 (Valid Palindrome II): allow one deletion. When mismatch at (left, right): try skipping left or skipping right. If either resulting substring is a palindrome: return True. LC 977 (Squares of Sorted Array): use two pointers at both ends, compare absolute values, fill result from the end (largest first). The squares of a sorted array are largest at the extremes (most negative or most positive elements).
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide