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
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the two pointers technique and when does it apply?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Two pointers uses two indices that traverse a data structure simultaneously, reducing O(n²) brute force to O(n). Three variants: (1) Opposite-end: left starts at 0, right at end, both move toward center. Apply when: sorted array, target sum, monotonic property (moving one pointer clearly improves/worsens the result). (2) Same-direction (sliding window): both pointers move left-to-right, maintaining a window. Apply when: "find subarray/substring with property" — right expands window, left shrinks when window violates constraint. (3) Fast/slow: one pointer advances 1 step, other advances 2 steps. Apply to: cycle detection, finding middle of linked list, nth-from-end removal. Recognition signal: sorted array + target, or "longest/shortest subarray/substring with constraint."”}},{“@type”:”Question”,”name”:”How do you solve 3Sum (LC 15) and 4Sum (LC 18)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”3Sum: sort the array. For each index i, run opposite-end two pointers on nums[i+1..n-1] looking for pairs that sum to -nums[i]. Skip duplicate values of nums[i] (outer loop) and skip duplicates of nums[l] and nums[r] (inner loop after finding a triplet). Time O(n²). 4Sum (LC 18): add another outer loop. For each pair (i, j), run two pointers on nums[j+1..n-1] looking for pairs summing to target – nums[i] – nums[j]. Skip duplicates at each level. Time O(n³). General pattern: k-sum reduces to (k-2)-sum using k-2 nested loops + two pointers for the innermost two elements. O(n^(k-1)) time.”}},{“@type”:”Question”,”name”:”How does the sliding window solve Minimum Window Substring (LC 76)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sliding window with character frequency tracking. need = Counter(t), missing = len(t). Expand right pointer: for each character added, if need[c] > 0, decrement missing (satisfied one required character). When missing == 0 (all required chars in window): shrink from left while the leftmost character is not needed (need[s[l]] < 0 means we have more than required). Record window size. Remove left character: increment need[s[l]] and increment missing if need[s[l]] > 0. Advance left. Repeat. Time O(n + m) where n = len(s), m = len(t). Key: the need counter goes negative when we have extras — only increment missing when need[c] goes from 0 to 1 (losing a required character). This avoids O(|t|) checks per step.”}},{“@type”:”Question”,”name”:”How do opposite-end two pointers solve Container With Most Water (LC 11)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Area = min(height[l], height[r]) * (r – l). To maximize: we want to maximize both the width (r – l) and the height (min of the two sides). Start with maximum width (l=0, r=n-1). On each step, we must narrow the width by 1 (either l++ or r–). The current limiting factor is min(height[l], height[r]). Moving the taller side inward can only decrease or maintain the height while reducing width — strictly worse. Moving the shorter side inward might find a taller bar, which could compensate for the reduced width. Therefore: always move the pointer on the shorter side. This greedy choice is correct: we never discard a pair that could be optimal. Time O(n).”}},{“@type”:”Question”,”name”:”How do you use two pointers on two sorted arrays?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Merge (merge sort step): pointer i on array A, pointer j on array B. Compare A[i] and B[j], append the smaller to result, advance that pointer. O(m+n). Intersection (LC 349): same merge-like traversal — when A[i] == B[j], it's in both arrays (add to result, advance both); else advance the pointer on the smaller value. Smallest Range Covering k Lists (LC 632): generalize to k pointers using a min-heap. Maintain the current window [min, max] across all k lists. Advance the pointer in the list with the current minimum (removing it from the heap, adding the next element). Track the minimum window seen. Stop when any list is exhausted.”}}]}
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.