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 waterSee also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: LinkedIn Interview Prep