Two PointersTwo pointers
Pointers closing in from both ends, or both moving the same way.
Used for: Pairs in a sorted array, deduplication, palindrome checks
01Why it exists
A ledger of transactions sorted by amount, and you need the two entries that add up to a reconciliation figure. Brute force pairs every entry with every other one: n(n−1)/2 pairs, O(n²).
Why this fitsSorted data has structure you can exploit. If the smallest plus the largest is too small, the smallest cannot reach the target with any partner at all, so it is eliminated; if the sum is too large, the largest goes instead. One pointer from the left and one from the right close in on each other, eliminating one element per step, so it is over in at most n − 1 steps. This is the standard answer for pairing in sorted data.
A sorted array contains duplicates that have to go, and you cannot allocate a second array (memory is tight, or the interface demands an in-place edit).
Why this fitsOne pointer reads ahead while the other tracks how far the writing has got. The read pointer is never behind the write pointer, so overwriting never damages data you have not read yet. These are same-direction pointers: O(n) time and O(1) extra space.
Decide whether a string reads the same forwards and backwards; or combine two individually sorted lists into a single sorted one.
Why this fitsA palindrome check compares from both ends inward, and a merge walks one pointer along each list. Both advance on the relationship between two positions, with no nested loop anywhere in sight.
Reach for it when you see:Already sorted, pairing things up, both ends closing in, editing in place, a nested O(n²) loop whose two indices move monotonically.
02The core idea
Two pointers is a technique for collapsing two nested loops into one: two indices move across the array, but every step moves in one direction only, so their combined travel never exceeds 2n and the whole scan is O(n). A brute-force double loop is O(n²) because the inner loop rescans a whole stretch every time the outer one moves; two pointers save that work because the problem has a monotonicity that makes going back unnecessary.
Converging pointers start at the far left and the far right and move toward each other. Take two sum on a sorted array: when a[l] + a[r] is too small, a[r] is already the largest value left, so a[l] cannot reach the target with any remaining partner (pairings with eliminated elements were ruled out long ago) and can be discarded safely; when the sum is too large, the same reasoning discards a[r]. One element is eliminated per step, and the elimination is provable — that, rather than "it looks reasonable", is why the method is correct. The precondition is that the data is sorted; unsorted data has to be sorted first, or handled with a hash table instead. Bear in mind that sorting scrambles the original indices, so when a problem wants those back (LeetCode 1, for instance) either carry the indices through the sort or reach for a hash table.
Same-direction pointers (fast and slow): both move right, one reading and one writing, or one scouting ahead while the other follows. When removing duplicates, w is the next slot to write and r reads forward; if a[r] differs from the last value kept, it gets written to a[w]. Because w ≤ r always holds, the cell being overwritten has already been read. Moving zeroes, filtering and compressing a string all share this skeleton.
How this relates to the sliding window: a sliding window is same-direction two pointers, with the range between the pointers carrying a particular meaning (the window). How it relates to binary search: both rely on ordering, but binary search halves the range to locate one position, while two pointers eliminate one element at a time to locate a pair. 3Sum pins one loop in place and runs converging pointers inside it, trading O(n³) for O(n²).
03The algorithm
- 1For converging pointers, ask first: is the data sorted? If it is not and the problem allows it, sort (O(n log n)); if it does not, consider a hash table. Same-direction problems such as moving zeroes or filtering need no ordering at all.
- 2Converging:
l = 0,r = n − 1,while l < r. Comparea[l] + a[r]against the target. - 3Too small means
l += 1, too large meansr −= 1, and equal is the answer. At every step, ask yourself why the eliminated element cannot work with any partner. - 4Same direction:
w = 0(or 1),for r in range(n). Whena[r]is worth keeping, doa[w] = a[r]; w += 1. - 5At the end, converging pointers return the pair they found or report that there is none; same-direction pointers return
w, anda[:w]is the result.
04Interactive demo
The "Converging" mode looks for a two sum of 25 in a sorted array, and the struck-out cells are the ones that have been proved impossible. The "Same direction" mode removes duplicates in place: green is the result written so far and amber is the position being read — notice that w never gets ahead of r.
A struck-through cell has been ruled out: it cannot be part of any answer, so it is never looked at again.
05Code
Two sum with converging pointers, duplicate removal with same-direction pointers, and 3Sum, which pins one value and converges on the other two. Deduplication is the easiest part of 3Sum to get wrong, so look closely at the two places where repeats are skipped.
# Converging pointers: two sum on a sorted array, returning 0-based indices
# (LeetCode 167 wants them 1-based, so add 1 to each before submitting)
def two_sum_sorted(nums, target):
l, r = 0, len(nums) - 1
while l < r:
s = nums[l] + nums[r]
if s == target:
return [l, r]
if s < target:
l += 1 # nums[l] falls short even with the largest partner, so drop it
else:
r -= 1 # nums[r] overshoots even with the smallest partner, so drop it
return [-1, -1]
# Same-direction pointers: remove duplicates from a sorted array in place (LeetCode 26), returning the new length
# w is the next slot to write to; r does the reading
def remove_duplicates(nums):
if not nums:
return 0
w = 1
for r in range(1, len(nums)):
if nums[r] != nums[w - 1]: # only a value unlike the last one kept is new
nums[w] = nums[r]
w += 1
return w # nums[:w] is the result
# Another classic for converging pointers: 3Sum (LeetCode 15)
# Sort, pin one value, and squeeze the remaining two with a two-sum scan
def three_sum(nums):
nums.sort()
out = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip a repeated first value
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
out.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1 # skip a repeated second value
return out
if __name__ == "__main__":
print(two_sum_sorted([2, 3, 5, 8, 11, 14, 17, 21], 25)) # [3, 6]
a = [1, 1, 2, 2, 2, 3, 5, 5, 6, 6]
n = remove_duplicates(a)
print(a[:n]) # [1, 2, 3, 5, 6]
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]06Practice
- LeetCode 167Two Sum II - Input Array Is SortedMedium
- LeetCode 26Remove Duplicates from Sorted ArrayEasy
- LeetCode 283Move Zeroes (same direction: a read and a write pointer)Easy
- LeetCode 125Valid PalindromeEasy
- LeetCode 153SumMedium
- LeetCode 11Container With Most Water (drop the shorter side)Medium