What you will learn
- When two pointers replace a nested loop.
- How to argue that moving a pointer never skips the answer.
- 3Sum with duplicate handling, and container with most water.
Signals
- The input is sorted (or you can sort it) and you need pairs or triples with a target sum.
- The problem is symmetric: palindromes, reversing, comparing both ends.
- You need to partition in place (move zeroes, Dutch flag).
Template
lo, hi = 0, len(a) - 1
while lo < hi:
if condition_met(a[lo], a[hi]):
record_answer()
elif need_bigger:
lo += 1
else:
hi -= 1
Each step discards one element for good, so the loop is O(n).
Code
"""Two pointers on sorted or symmetric input."""
def pair_with_sum(sorted_nums, target):
lo, hi = 0, len(sorted_nums) - 1
while lo < hi:
s = sorted_nums[lo] + sorted_nums[hi]
if s == target:
return lo, hi
if s < target:
lo += 1 # need a bigger sum: only moving lo right can help
else:
hi -= 1 # need a smaller sum
return None
def three_sum(nums):
nums = sorted(nums)
out = []
for i in range(len(nums) - 2):
if i and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0:
lo += 1
elif s > 0:
hi -= 1
else:
out.append([nums[i], nums[lo], nums[hi]])
lo += 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return out
def max_water(heights):
lo, hi, best = 0, len(heights) - 1, 0
while lo < hi:
best = max(best, (hi - lo) * min(heights[lo], heights[hi]))
if heights[lo] < heights[hi]:
lo += 1 # the shorter wall limits the area; moving the taller one can't help
else:
hi -= 1
return best
if __name__ == "__main__":
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))
print(three_sum([-1, 0, 1, 2, -1, -4]))
print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))
Output:
(2, 3)
[[-1, -1, 2], [-1, 0, 1]]
49
Why the moves are safe
- Pair sum: if
a[lo] + a[hi]is too small, pairinga[lo]with anything left ofhiis even smaller, soa[lo]can’t be in any answer. Discard it. - 3Sum: sort, fix the first number, then run pair sum on the rest. Skip equal anchors and equal
lovalues to avoid duplicate triples. O(n²) overall, the best known for this problem in practice. - Container with most water: the area is limited by the shorter wall. Moving the taller wall inward can only shrink the width without raising that limit, so always move the shorter one.
Being able to state this “why” is what interviewers listen for.
Variants
- Same direction (read/write pointers): remove duplicates in place, move zeroes. One pointer scans, the other marks where to write.
- Opposite ends on strings: valid palindrome, reverse vowels.
- When the window between pointers must satisfy a condition, that’s the sliding window pattern.
Practise: two pointers problems.
Key takeaways
- Two pointers work when each comparison lets you discard an element for good.
- Sort first if order doesn’t matter to the answer; it costs O(n log n).
- In 3Sum, deduplicate by skipping equal neighbours, not by using a set of tuples.
- Always be able to explain why a pointer move can’t skip the answer.
Exercises
- Solve “valid palindrome” ignoring non-alphanumeric characters with two pointers.
- Write “move zeroes” with read/write pointers, keeping the order of non-zero elements.
- Extend
three_sumto 4Sum. What’s the complexity?
Quiz
- Why must the array be sorted for pair sum with two pointers?
- In container with most water, why move the shorter wall?
- What’s the time complexity of 3Sum with this approach?
Show answers
- Sorting guarantees that moving
loright increases the sum and movinghileft decreases it, which is what makes discarding safe. - The shorter wall caps the height; moving the taller wall can only reduce width while the cap stays the same or lower.
- O(n²): O(n log n) to sort plus an O(n) scan for each of n anchors.