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).
{
“@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”: “Two pointers: requires the array to be sorted (or have a monotonic property). Provides O(1) space. Hash map: works on unsorted arrays. Uses O(n) space. Decision rule: if the problem requires an unsorted array and you can’t sort it: use a hash map. If sorting is acceptable (or the array is already sorted) and space is a concern: use two pointers. Example: Two Sum on an unsorted array where you must return indices (LC 1): can’t sort without losing original indices u2192 use hash map. Two Sum on a sorted array (LC 167): sorted u2192 two pointers, O(1) space. Three Sum (LC 15): sort first (indices don’t matter, we return values) u2192 two pointers for the inner loop. Practical interview tip: when you see a problem on a sorted array asking for pairs or triplets summing to a target, immediately think two pointers. When you see an unsorted array with a sum constraint, think hash map. Both are O(n) for two sum; two pointers is O(n^2) for three sum, but there’s no known O(n) algorithm for 3Sum, so it’s optimal.”
}
},
{
“@type”: “Question”,
“name”: “How does the two-pointer approach work for the Dutch National Flag problem (LC 75)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Sort an array of 0s, 1s, and 2s in-place using a single pass. Three-pointer variant: low (boundary for 0s), mid (current element), high (boundary for 2s). Invariant: nums[0..low-1]=0, nums[low..mid-1]=1, nums[high+1..n-1]=2, nums[mid..high] unprocessed. Process: while mid <= high: if nums[mid]==0: swap nums[low] and nums[mid], low++, mid++. If nums[mid]==1: mid++. If nums[mid]==2: swap nums[mid] and nums[high], high– (don't increment mid — the swapped element is unprocessed). Why don't we increment mid after swapping a 2? The element swapped from high is unknown — it could be a 0, 1, or 2. We must process it. The element swapped from low is known to be 0 or 1 (it was already processed) — so after swapping a 0, we can safely increment both low and mid. This single-pass O(n) O(1) space solution is the canonical answer to "sort 3 values in one pass.""
}
},
{
"@type": "Question",
"name": "How do you find all pairs in an array that sum to a target (not just one pair)?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Depends on whether the array is sorted and whether duplicates are allowed. Sorted array, distinct elements: two pointers. When sum == target: record the pair, move both pointers (left++, right–). When sum target: right–. O(n). Sorted array, duplicates allowed, unique pairs required: after recording a pair at (left, right), skip all duplicates: while nums[left] == nums[left+1]: left++. while nums[right] == nums[right-1]: right–. Then left++, right–. Unsorted array, return all pairs (including duplicate values): sort first (if duplicates matter), then apply the above. If you need to preserve indices: hash map approach — for each element, check if target – element is in the map. Collect all (i, j) pairs where i < j. Count pairs only (not the pairs themselves): use a frequency map. For value v: pair_count += freq[target-v] (if target-v != v), or freq[v] * (freq[v]-1) / 2 (if target-v == v). O(n) time and space."
}
},
{
"@type": "Question",
"name": "What is the fast and slow pointer technique and what problems does it solve?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Fast and slow pointers (Floyd's cycle detection): slow advances 1 step at a time; fast advances 2 steps. If there is a cycle: fast will eventually lap slow and they will meet. If there is no cycle: fast reaches the end of the list (or null). Applications: (1) Detect cycle in linked list (LC 141): if fast and slow meet: cycle exists. O(n) time, O(1) space. (2) Find the entry point of the cycle (LC 142): after detecting the meeting point, move one pointer to the head. Advance both at 1 step. They meet at the cycle entry. (3) Find the middle of a linked list (LC 876): when fast reaches the end (or null), slow is at the middle. (4) Detect cycle and find duplicate in an array (LC 287 Find the Duplicate Number): treat the array as a linked list where array[i] is the "next pointer." The duplicate creates a cycle. Apply Floyd's to find the duplicate without modifying the array (O(n) time, O(1) space). Key insight for cycle detection: slow travels distance d; fast travels 2d. If there is a cycle of length c: fast laps slow when 2d – d = kc u2192 d = kc. They must meet within the cycle."
}
},
{
"@type": "Question",
"name": "How do you solve the minimum operations to reduce X to zero problem (LC 1658) with two pointers?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Remove elements from either the left or right end of an array such that their sum equals X. Minimize the number of elements removed. Rephrase: find the longest subarray with sum = total_sum – X. This transforms the problem into a sliding window maximum problem. If total_sum – X target: remove nums[left], left++. When window_sum == target: update max_length. Answer: n – max_length. O(n) time, O(1) space. The key transformation: “minimize removed from both ends with sum X” u2194 “maximize retained middle with sum total-X.” This rephrase-to-complement trick appears in several problems: whenever the problem involves minimizing the “outside” of a subarray, think about maximizing the “inside.””
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide