3Sum
StopTwo pointers
16/16
Fix one number, then run two pointers over the rest for its negative.
Step through it →Two Pointers
Two pointers start at both ends of a sorted list and walk inward, and every step rules out every pair one number could still make.
Two Sum II: find the pair that adds up to the target
StopTwo pointers
numberstarget
- CH1 left
- CH2 right
Start at both ends: 2, the smallest number, and 15, the largest.
Typical cost O(n) time (after any sort), O(1) spaceFull lesson: Two Sum II - Input Array Is Sorted →
When to reach for it
- The input is sorted, or sorting it costs less than the loop it saves.
- You want a pair or triple that hits a target.
- The two ends alone tell you which one to move.
- You compare from both ends: palindromes, reversals, walls that hold water.
- The brute force checks every pair in a nested loop.
What stays true
When the sum is too big, the right number is too big even for the smallest partner left, so no pair can use it. When it's too small, the same goes for the left number. Each move drops one number for good.
Nothing ruled out was ever part of the answer
StopTwo pointers
InvariantIf a pair hits the target, it is still between left and right.✓ Holds
- CH1 left
- CH2 right
Start at both ends: 1, the smallest number, and 11, the largest.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
A loop that runs while left ≤ right pairs 3 with itself and answers 3 + 3. This one stops when the pointers meet.
Two Sum II on the inputs that trip it up
StopTwo pointers
- CH1 left
- CH2 right
Start at both ends: 3, the smallest number, and 5, the largest.
Answer[]Steps4
Variants
Container with most water
StopTwo pointers
- CH1 left
- CH2 right
- CH4 water
10/10
Move the shorter wall. Keeping it can only lose width.
Step through it →Trapping rain water
StopTwo pointers
- CH1 left
- CH2 right
- CH4 water
14/14
Move the lower side. Its water level is already decided.
Step through it →Valid palindrome
StopTwo pointers
- CH1 left
- CH2 right
11/11
Compare the two ends, skipping anything that isn't a letter or digit.
Step through it →The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Two Sum II: find the pair that adds up to the target
StopTwo pointers
- CH1 left
- CH2 right
Start at both ends: 2, the smallest number, and 15, the largest.
two_sum_sorted.py
def two_sum(numbers, target): left, right = 0, len(numbers) - 1 while left < right: total = numbers[left] + numbers[right] if total == target: return [left + 1, right + 1] if total > target: right -= 1 else: left += 1 return []