Lessons · Python · two pointers
Two fingers, one pass
Instead of comparing every pair with two nested loops, put one index at each end and move them toward each other, deciding at each step which one to move.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
It turns a scan of every pair, which is n squared, into a single pass. The catch is that it only works when order tells you something, which usually means the data is sorted or can be.
How to think about it
Ask what the current pair tells you. If it is safe to conclude that one of the two can never be part of any answer, move that pointer past it. If you cannot say that, two pointers is the wrong tool.
Worked example
def pair_summing_to(values, target):values is SORTED; that is what makes this safe.
left, right = 0, len(values) - 1One at each end.
while left < right:Stop when they meet.
total = values[left] + values[right]
if total == target: return (values[left], values[right])Found it.
if total < target: left += 1Too small: only a bigger left can help.
else: right -= 1Too big: only a smaller right can help.
return None
print(pair_summing_to([1, 3, 5, 8, 12], 17))(5, 12)
print(pair_summing_to([1, 3, 5, 8, 12], 100))None
Your turn
The pair is too small; move the pointer that can help.
if total < target:
+= 1
else:
right -= 1Solve one with the tests running
The trap
On UNSORTED data the move is not safe: skipping past a value throws away a real answer, and the function returns None with total confidence.