Two Pointers Fundamentals
Two pointers use two indices traversing an array or string to solve problems in O(n) that would otherwise require O(n^2). The key insight: when the array is sorted or has some structural property, two pointers converging from opposite ends (or moving in the same direction at different speeds) can eliminate the need for a nested loop. Two pointer problems appear in roughly 10-15% of coding interviews and frequently disguise as array, string, or linked list problems.
Pattern 1: Opposite Ends (Two-Sum Variant)
Start one pointer at the left end and one at the right end of a sorted array. Move them toward each other based on comparison.
# Two Sum II (sorted array): find pair summing to target
def two_sum_sorted(numbers: list, target: int) -> list:
left, right = 0, len(numbers) - 1
while left < right:
curr = numbers[left] + numbers[right]
if curr == target:
return [left + 1, right + 1] # 1-indexed
elif curr int:
left, right = 0, len(height) - 1
max_water = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
max_water = max(max_water, water)
if height[left] < height[right]:
left += 1 # move shorter side inward to find a taller wall
else:
right -= 1
return max_water
Pattern 2: Three Sum and K Sum
# Three Sum: find all unique triplets summing to 0
def three_sum(nums: list) -> list:
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # skip duplicates for outer element
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 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 total < 0:
left += 1
else:
right -= 1
return result
# Pattern: sort first, fix one element, use two pointers for the rest
# Generalizes to 4Sum: fix two elements (nested loops), two pointers for remaining pair
Pattern 3: Same Direction (Partition / Filter)
# Remove duplicates from sorted array in-place
def remove_duplicates(nums: list) -> int:
if not nums: return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Move zeros to end (maintain relative order of non-zeros)
def move_zeroes(nums: list) -> None:
slow = 0 # next position to place a non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
# Partition: Dutch National Flag (sort array of 0s, 1s, 2s)
def sort_colors(nums: list) -> None:
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # do not increment mid (newly swapped element unchecked)
Pattern 4: Trapping Rain Water
Classic O(n) two pointer solution: water at position i equals min(max height to the left, max height to the right) minus height[i]. Pre-computing left and right max arrays works but uses O(n) space. Two pointers achieve O(1) space by processing from the side with the smaller max height — that side determines the water level, independent of unseen heights on the other side.
def trap(height: list) -> int:
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] = left_max:
left_max = height[left] # update max, no water here
else:
water += left_max - height[left] # trapped water
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
Pattern 5: Palindrome Verification
# Valid Palindrome (ignore non-alphanumeric)
def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum(): left += 1
while left str:
def expand(l, r):
while l >= 0 and r len(result): result = odd
# Even length: expand from two centers
even = expand(i, i + 1)
if len(even) > len(result): result = even
return result
Common Two Pointer Problems
- Opposite ends: Two Sum II, Container With Most Water, Valid Palindrome, Reverse a String
- K-sum: Three Sum, Three Sum Closest, Four Sum
- Same direction: Remove Duplicates, Move Zeroes, Remove Element, Squares of Sorted Array
- Partition: Sort Colors (Dutch National Flag), Partition Array
- Rain water: Trapping Rain Water (two pointer or stack)
- Palindrome: Valid Palindrome, Palindromic Substrings, Longest Palindromic Substring
Frequently Asked Questions
When should you use two pointers instead of a hash map?
Use two pointers when the array is sorted (or can be sorted without losing information) and the problem asks about pairs or subarrays. Two pointers achieves O(n) time and O(1) space — better than a hash map's O(n) space. Use a hash map when the array is unsorted and sorting would destroy necessary index information, or when you need to track element frequency. Classic two-pointer problems: Two Sum II (sorted input), Container With Most Water, Trapping Rain Water, 3Sum (sort first, then fix one element and use two pointers on the rest). Classic hash map problems: Two Sum I (unsorted, need original indices), longest substring without repeating characters (need to track position), group anagrams. The sorting requirement is the key distinguisher: if sorting is acceptable, two pointers is usually cleaner and uses less memory.
How does the three-sum algorithm avoid duplicates efficiently?
Sort the array first. For each index i (the fixed element), use two pointers left=i+1 and right=n-1 to find pairs that sum to -nums[i]. When a valid triplet is found, advance left and right simultaneously while skipping duplicate values (while left < right and nums[left] == nums[left-1], left++). Similarly, skip duplicates for the outer loop (if i > 0 and nums[i] == nums[i-1], continue). Sorting ensures that duplicates are adjacent, making the skip logic a simple while loop instead of a hash set lookup. This gives O(n^2) time and O(1) extra space (excluding output). Without sorting, you would need a hash set of seen triplets for deduplication, adding O(n) space and string comparison overhead. The sort-and-skip pattern applies to k-sum problems generally: sort once, recurse for k-2 elements, apply two pointers at the innermost level.
How do you solve Trapping Rain Water with two pointers?
The water above each position equals min(maxLeft, maxRight) – height[position]. A brute force precomputes maxLeft and maxRight arrays in O(n) space. The two-pointer approach eliminates the extra arrays. Maintain left and right pointers at the array ends, and track maxLeft and maxRight seen so far. At each step: if height[left] < height[right], the water at left is determined by maxLeft (because maxRight is at least height[right] > height[left], so it is not the limiting factor). Water at left = max(0, maxLeft – height[left]). Advance left. Otherwise, the water at right is determined by maxRight. Advance right. Each position is processed once: O(n) time, O(1) space. This works because when height[left] < height[right], we know the right boundary is at least height[right], so maxLeft is the binding constraint — we can safely compute the water at left without knowing the actual maximum to the right.
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “When should you use two pointers instead of a hash map?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Use two pointers when the array is sorted (or can be sorted without losing information) and the problem asks about pairs or subarrays. Two pointers achieves O(n) time and O(1) space — better than a hash map’s O(n) space. Use a hash map when the array is unsorted and sorting would destroy necessary index information, or when you need to track element frequency. Classic two-pointer problems: Two Sum II (sorted input), Container With Most Water, Trapping Rain Water, 3Sum (sort first, then fix one element and use two pointers on the rest). Classic hash map problems: Two Sum I (unsorted, need original indices), longest substring without repeating characters (need to track position), group anagrams. The sorting requirement is the key distinguisher: if sorting is acceptable, two pointers is usually cleaner and uses less memory.” } }, { “@type”: “Question”, “name”: “How does the three-sum algorithm avoid duplicates efficiently?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Sort the array first. For each index i (the fixed element), use two pointers left=i+1 and right=n-1 to find pairs that sum to -nums[i]. When a valid triplet is found, advance left and right simultaneously while skipping duplicate values (while left 0 and nums[i] == nums[i-1], continue). Sorting ensures that duplicates are adjacent, making the skip logic a simple while loop instead of a hash set lookup. This gives O(n^2) time and O(1) extra space (excluding output). Without sorting, you would need a hash set of seen triplets for deduplication, adding O(n) space and string comparison overhead. The sort-and-skip pattern applies to k-sum problems generally: sort once, recurse for k-2 elements, apply two pointers at the innermost level.” } }, { “@type”: “Question”, “name”: “How do you solve Trapping Rain Water with two pointers?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “The water above each position equals min(maxLeft, maxRight) – height[position]. A brute force precomputes maxLeft and maxRight arrays in O(n) space. The two-pointer approach eliminates the extra arrays. Maintain left and right pointers at the array ends, and track maxLeft and maxRight seen so far. At each step: if height[left] height[left], so it is not the limiting factor). Water at left = max(0, maxLeft – height[left]). Advance left. Otherwise, the water at right is determined by maxRight. Advance right. Each position is processed once: O(n) time, O(1) space. This works because when height[left] < height[right], we know the right boundary is at least height[right], so maxLeft is the binding constraint — we can safely compute the water at left without knowing the actual maximum to the right." } } ] }