- Solve 3Sum by reducing it to n iterations of 2Sum
- Handle duplicates correctly when finding unique combinations
- Use two pointers for in-place array modifications (remove duplicates, move zeros)
- Apply opposite-ends strategy for problems like container with most water
Two Pointers for Array Problems
Arrays are where two pointers really proves its worth. Let's work through the classic problems, understand why the technique works, and see how to apply it.
The 3Sum Problem
Finding two numbers that sum to a target is straightforward with two pointers. But what about three numbers?
Given an array, find all unique triplets that sum to zero. For example, in [-1, 0, 1, 2, -1, -4], the answer is [[-1, -1, 2], [-1, 0, 1]].
The naive approach uses three nested loops—that's O(n³). For n=100, that's a million operations. For n=1000, a billion.
The two pointer approach reduces this to O(n²):
def three_sum(nums):
nums.sort() # O(n log n)
result = []
for i in range(len(nums) - 2):
# Skip duplicate values for the first element
if i > 0 and nums[i] == nums[i-1]:
continue
# Now it's a two-sum problem with target = -nums[i]
left, right = i + 1, len(nums) - 1
target = -nums[i]
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates for second element
while left < right and nums[left] == nums[left + 1]:
left += 1
# Skip duplicates for third element
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif current_sum < target:
left += 1
else:
right -= 1
return result
Let's trace through [-1, 0, 1, 2, -1, -4]:
First, sort: [-4, -1, -1, 0, 1, 2]
i=0, nums[0]=-4, target=4
left=1, right=5: -1+2=1<4, left++
left=2, right=5: -1+2=1<4, left++
left=3, right=5: 0+2=2<4, left++
left=4, right=5: 1+2=3<4, left++
left=5, right=5: done
i=1, nums[1]=-1, target=1
left=2, right=5: -1+2=1, found! → [-1, -1, 2]
Skip nums[2]=-1 (duplicate)
left=3, right=4: 0+1=1, found! → [-1, 0, 1]
i=2, skip (nums[2]==-1, duplicate of nums[1])
i=3, nums[3]=0, target=0
left=4, right=5: 1+2=3>0, right--
left=4, right=4: done
Result: [[-1, -1, 2], [-1, 0, 1]]
The key insight: fix one element, then use two pointers for the remaining two. We've turned a 3-way problem into n iterations of a 2-way problem.
Squaring a Sorted Array
You have a sorted array (possibly with negatives) like [-4, -1, 0, 3, 10]. Return the squares in sorted order: [0, 1, 9, 16, 100].
The catch: the array can have negative numbers. Squaring them makes them positive, and the largest squares might come from the most negative or most positive numbers.
Naive approach: square everything, sort. That's O(n log n).
Two pointers: work backwards from the largest squares.
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1 # Fill result from right to left
while left <= right:
left_square = nums[left] * nums[left]
right_square = nums[right] * nums[right]
if left_square > right_square:
result[pos] = left_square
left += 1
else:
result[pos] = right_square
right -= 1
pos -= 1
return result
For [-4, -1, 0, 3, 10]:
left=0(-4), right=4(10), pos=4
16 vs 100: place 100 at result[4], right=3
left=0(-4), right=3(3), pos=3
16 vs 9: place 16 at result[3], left=1
left=1(-1), right=3(3), pos=2
1 vs 9: place 9 at result[2], right=2
left=1(-1), right=2(0), pos=1
1 vs 0: place 1 at result[1], left=2
left=2(0), right=2(0), pos=0
0 vs 0: place 0 at result[0], done
Result: [0, 1, 9, 16, 100]
This is O(n) time with O(n) space for the result. The key: the largest square is always at one of the ends.
Removing Duplicates In-Place
You have a sorted array [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]. Remove duplicates in-place so the first k elements are unique, and return k.
The constraint: O(1) extra space. You can't create a new array.
Use two pointers: slow tracks where to place the next unique element, fast scans for unique elements.
def remove_duplicates(nums):
if not nums:
return 0
slow = 0 # Position for next unique element
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # Length of unique portion
For [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:
slow=0, fast=1: nums[1]=0 == nums[0]=0, skip
slow=0, fast=2: nums[2]=1 != nums[0]=0, slow=1, nums[1]=1
Array: [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
slow=1, fast=3: nums[3]=1 == nums[1]=1, skip
slow=1, fast=4: nums[4]=1 == nums[1]=1, skip
slow=1, fast=5: nums[5]=2 != nums[1]=1, slow=2, nums[2]=2
Array: [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
slow=2, fast=6: nums[6]=2 == nums[2]=2, skip
slow=2, fast=7: nums[7]=3 != nums[2]=2, slow=3, nums[3]=3
Array: [0, 1, 2, 3, 1, 2, 2, 3, 3, 4]
slow=3, fast=8: nums[8]=3 == nums[3]=3, skip
slow=3, fast=9: nums[9]=4 != nums[3]=3, slow=4, nums[4]=4
Array: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
Return 5 (first 5 elements are unique: [0, 1, 2, 3, 4])
The slow pointer marks the boundary of the unique section. Everything from 0 to slow (inclusive) is unique and sorted.
Merging Two Sorted Arrays
You're given [1, 3, 5] and [2, 4, 6]. Merge them into [1, 2, 3, 4, 5, 6].
This is how merge sort's merge step works:
def merge(arr1, arr2):
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# Append remaining elements
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
For [1, 3, 5] and [2, 4, 6]:
i=0(1), j=0(2): 1<2, take 1, i++, result=[1]
i=1(3), j=0(2): 3>2, take 2, j++, result=[1,2]
i=1(3), j=1(4): 3<4, take 3, i++, result=[1,2,3]
i=2(5), j=1(4): 5>4, take 4, j++, result=[1,2,3,4]
i=2(5), j=2(6): 5<6, take 5, i++, result=[1,2,3,4,5]
i=3, append remaining from arr2: result=[1,2,3,4,5,6]
Each element is visited once. O(n+m) time, where n and m are the array lengths.
Container With Most Water
You have heights [1, 8, 6, 2, 5, 4, 8, 3, 7]. Think of them as vertical lines. Which two lines form a container that holds the most water?
The area is min(height[left], height[right]) × (right - left). Width decreases as pointers move inward, so we need to find taller lines to compensate.
Strategy: start with the widest container (left=0, right=end). Move the pointer at the shorter height inward, hoping to find a taller line.
def max_area(heights):
left, right = 0, len(heights) - 1
max_water = 0
while left < right:
width = right - left
height = min(heights[left], heights[right])
max_water = max(max_water, width * height)
# Move the shorter line inward
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return max_water
For [1, 8, 6, 2, 5, 4, 8, 3, 7]:
left=0(1), right=8(7): area=min(1,7)*8=8, move left (shorter)
left=1(8), right=8(7): area=min(8,7)*7=49, move right (shorter)
left=1(8), right=7(3): area=min(8,3)*6=18, move right (shorter)
left=1(8), right=6(8): area=min(8,8)*5=40, move either (same height)
...
Max area found: 49
Why move the shorter height? Because the area is limited by the shorter line. If you move the taller line inward, you lose width but can't gain height (still limited by the shorter line). Moving the shorter line at least gives you a chance to find a taller line that could increase the area despite the lost width.
Move Zeros to End
Given [0, 1, 0, 3, 12], move all zeros to the end while maintaining the order of non-zero elements: [1, 3, 12, 0, 0].
This is similar to removing duplicates:
def move_zeros(nums):
slow = 0 # Position for next non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
For [0, 1, 0, 3, 12]:
slow=0, fast=0: nums[0]=0, skip
slow=0, fast=1: nums[1]=1, swap(0,1), [1,0,0,3,12], slow=1
slow=1, fast=2: nums[2]=0, skip
slow=1, fast=3: nums[3]=3, swap(1,3), [1,3,0,0,12], slow=2
slow=2, fast=4: nums[4]=12, swap(2,4), [1,3,12,0,0], slow=3
Result: [1, 3, 12, 0, 0]
The slow pointer marks where the next non-zero should go. We swap non-zeros to the front, and zeros naturally accumulate at the end.
Common Mistakes
Not handling duplicates: In 3Sum, forgetting to skip duplicates leads to duplicate triplets in the result.
Wrong pointer to move: In container with most water, moving the taller line can never improve the area.
Boundary errors: Off-by-one mistakes are common. Always double-check loop conditions and array bounds.
Forgetting to sort: Many two pointer techniques require sorted input. If it's not sorted, sort it first.
When to Use Two Pointers on Arrays
Ask yourself:
Is the array sorted? Or can you sort it without breaking the problem?
Do you need to find pairs or triplets? Two pointers excel at finding combinations.
Can you make a decision that eliminates possibilities? If comparing elements tells you which direction to move pointers, two pointers likely works.
Do you need O(1) space? Two pointers often works in-place, unlike hash maps.
The Pattern
Most two pointer array problems follow this structure:
- Sort if needed (unless already sorted or sorting breaks the problem)
- Initialize pointers (usually at ends or start)
- Loop while pointers valid (left < right, or similar condition)
- Compare elements at pointers
- Make a decision (move left, move right, or both)
- Handle edge cases (duplicates, boundaries, empty arrays)
Once you've solved a few of these problems, you'll start recognizing the pattern instantly. That's when two pointers stops being a technique you're learning and becomes a tool you reach for naturally.