Two Pointers
The Intuition
Imagine a sorted line of people, each holding a number card. You need to find two people whose numbers add up to, say, 42. You could check every possible pair, but that's slow. Instead, put one friend at the far left end of the line and another at the far right.
They add their numbers. Too big? The right friend steps one spot left, because moving toward smaller numbers is the only way to bring the sum down. Too small? The left friend steps right toward bigger numbers. They walk toward each other, and somewhere in the middle, they either find the pair or meet and confirm no pair exists. One pass. No wasted comparisons.
Why does this work and not miss valid pairs? Because the array is sorted. When the sum is too large, you know that pairing the right person with anyone further right would be even larger. So every pair involving the current right position and a left position further right is ruled out in one step. The same logic applies in reverse for the left pointer.
There's a second flavor of two pointers where both start at the same end and move in the same direction. Picture a "reader" scanning through an array and a "writer" that only advances when the reader finds something worth keeping. Removing duplicates from a sorted array works exactly like that. The reader skips over repeated values, and the writer stamps down each unique one. Two pointers, same direction, O(n) time, O(1) space.
Sorted array pair problems, partitioning, removing duplicates in-place, or any problem where examining elements from both ends narrows the search space.
- Unsorted data that can't be sorted
- Need all pairs not just one (use hash map)
- Non-linear relationships between elements
Variations:
- Opposite-direction pointers: Start at both ends, converge toward the middle (pair sum, container with most water).
- Same-direction pointers: A slow "write" pointer and a fast "read" pointer (remove duplicates, move zeroes).
- Three pointers: Extension for 3Sum problems where you fix one element and use two pointers on the rest.
- empty array
- all same values
- two elements
Key Points
- •Initialize pointers at opposite ends or same start
- •Move based on comparison with target
- •Handle duplicates by skipping equal elements
- •Works on sorted arrays for pair-finding problems
- •Can also use same-direction pointers for partitioning
Code Template
1 def two_pointers(arr, target):
2 """Find pair in sorted array that sums to target."""
3 left, right = 0, len(arr) - 1
4 while left < right:
5 current = arr[left] + arr[right]
6 if current == target:
7 return [left, right]
8 elif current < target:
9 left += 1
10 else:
11 right -= 1
12 return [-1, -1]
13
14 # Same-direction variant: remove duplicates in-place
15 def remove_duplicates(arr):
16 if not arr:
17 return 0
18 write = 1
19 for read in range(1, len(arr)):
20 if arr[read] != arr[read - 1]:
21 arr[write] = arr[read]
22 write += 1
23 return writeCommon Mistakes
- Infinite loop when both pointers aren't advancing
- Not handling duplicate elements properly
- Forgetting to sort the array when required