The Two Pointers Pattern
Two pointers uses two indices that move toward each other (or in the same direction) to reduce O(n^2) brute force to O(n). The pattern applies when: the array is sorted (or can be sorted), you are searching for pairs/triplets that satisfy a sum or distance constraint, and moving one pointer can deterministically improve the result. Two variants: Opposite ends: left starts at 0, right starts at n-1. Move toward each other based on the comparison. Used for pair sum, palindrome check, container with most water. Same direction (fast/slow): both start at 0 but move at different rates. Used for removing duplicates, finding cycle in linked list, merging sorted arrays.
Two Sum II — Sorted Array (LC 167)
def two_sum(numbers: list[int], target: int) -> list[int]:
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []Three Sum (LC 15) — Sort + Two Pointers
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate for first element
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 # skip duplicates
while left < right and nums[right] == nums[right - 1]:
right -= 1 # skip duplicates
left += 1; right -= 1
elif s < 0:
left += 1
else:
right -= 1
return resultContainer With Most Water (LC 11)
Two pointers from ends. Area = min(height[left], height[right]) * (right – left). Move the shorter side inward — moving the taller side cannot increase the area (width decreases and height is bounded by the same shorter bar or less). This greedy is correct by elimination: if left < right in height, keeping right and moving left forward is the only way to potentially increase the min height.
def max_area(height: list[int]) -> 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
else:
right -= 1
return max_waterRemove Duplicates and Partition (Fast/Slow Pointers)
# Remove duplicates from sorted array in-place (LC 26)
def remove_duplicates(nums: list[int]) -> int:
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Sort Colors / Dutch National Flag (LC 75)
def sort_colors(nums: list[int]) -> 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] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # don't advance mid - swapped element unseenTrapping Rain Water (LC 42)
Water at position i = min(max_left, max_right) – height[i]. Two pointers: track left_max and right_max. Process from whichever side has the smaller max — that side’s water level is guaranteed by the known max.
def trap(height: list[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
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 water
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”Why does the two-pointer approach work for Container With Most Water?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The area between two lines is min(height[left], height[right]) * (right – left). Starting with left=0 and right=n-1 gives the widest possible container. The key insight: to potentially find a larger area, we must increase the min height. Moving the pointer with the larger height inward cannot help — the width decreases AND the min height is still bounded by the shorter bar (or shorter). Moving the shorter bar inward might increase the min height, potentially compensating for the reduced width. This greedy elimination is correct: we never miss a better solution because for any fixed shorter bar, the widest container with that bar as the limiting factor has already been considered.”}},{“@type”:”Question”,”name”:”What is the deduplication strategy in 3Sum and why is it necessary?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Without deduplication, 3Sum returns duplicate triplets. Example: [-2, 0, 0, 2, 2] — the triplet [-2, 0, 2] would be found multiple times. Three deduplication points: (1) Outer loop: if nums[i] == nums[i-1] and i > 0, skip (same first element was already processed). (2) After finding a valid triplet: advance left past all duplicates (while left < right and nums[left] == nums[left+1]: left++). (3) Advance right past all duplicates (while left < right and nums[right] == nums[right-1]: right–). Then advance both pointers one more step. The sort is prerequisite — without it, duplicates are not adjacent and cannot be skipped with this technique. Time complexity: O(n^2) after the O(n log n) sort.”}},{“@type”:”Question”,”name”:”How do fast and slow pointers detect a cycle in a linked list?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Floyd's cycle detection (tortoise and hare): slow pointer advances 1 node per step; fast pointer advances 2. If there is a cycle: both pointers enter the cycle and fast catches up to slow within the cycle (fast gains 1 node per step on slow). They are guaranteed to meet because fast never jumps over slow — it approaches 1 step closer each iteration within the cycle. If there is no cycle: fast reaches NULL first. To find the cycle start: when slow and fast meet inside the cycle, reset one pointer to head. Advance both 1 step at a time. They meet at the cycle entry point. Proof: the distance from the meeting point to the cycle start equals the distance from head to the cycle start (mathematical property of the cycle lengths).”}},{“@type”:”Question”,”name”:”How does the Dutch National Flag algorithm partition an array in one pass?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Dutch National Flag (3-way partition by Dijkstra) uses 3 pointers: low (boundary of 0s), mid (current), high (boundary of 2s). Invariant: [0, low) = all 0s, [low, mid) = all 1s, [mid, high] = unsorted, (high, n-1] = all 2s. On each step: if nums[mid] == 0: swap with nums[low], advance both low and mid (the swapped-in value was already seen — it was a 1). If nums[mid] == 1: advance mid only. If nums[mid] == 2: swap with nums[high], advance high backward only — do NOT advance mid (the swapped-in value from position high has not been examined yet). Loop terminates when mid > high. O(n) time, O(1) space, exactly one pass.”}},{“@type”:”Question”,”name”:”Why does trapping rain water require knowing both left and right maximum heights?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Water at position i is bounded by the shorter of the two walls enclosing it: water[i] = min(max_height_left_of_i, max_height_right_of_i) – height[i]. You cannot compute this with only one direction of max. The two-pointer O(n) solution avoids storing full left_max and right_max arrays: maintain running left_max and right_max. When processing the left side (height[left] < height[right]): the right boundary is guaranteed to be at least height[right] (which is >= right_max seen so far on the right). So left_max is the actual limiting factor — compute water using left_max. Vice versa for the right side. The key insight: you process whichever side has the smaller known max, because that side's limit is deterministic even without knowing the other side's full maximum.”}}]}
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: LinkedIn Interview Prep