The Sorted Squeeze: Pairs in a Sorted List
A gym keeps its weight plates on a rack sorted from lightest to heaviest: 2, 5, 7, 11, 14 and 20 kg. A lifter wants two plates that add up to exactly 18 kg. You already know one answer, the complement lookup with a dictionary. But the rack is sorted, and sorted data lets you find the pair with no dictionary at all.
The rule
Sum too small, move left up; sum too big, move right down.
Point left at the lightest plate and right at the heaviest, and add them. Too heavy? The heaviest plate is the problem, so step right down. Too light? Step left up. Just right? Done.
def sorted_pair(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return (left, right)
if total < target:
left += 1 # need more: the smallest value cannot help
else:
right -= 1 # need less: the largest value cannot help
return NoneWhy is it safe to throw a value away? Suppose the total is too big. nums[right] is being added to the smallest value still in play, and the result is already too big, so with any other partner it would be even bigger. It can never be part of the answer, and dropping it loses nothing. The same argument, flipped, covers a total that is too small.
Each step drops one value, so the loop runs at most n times, and the only extra memory is two integers. Compared with the dictionary, you trade "needs sorted input" for "needs no extra memory".
The shortcut
Read each step as a compare-and-drop: compare the total with the target, then drop the value on the side that caused the miss. You never go back, because a dropped value has been proven useless.
2 + 20 = 22
Too big. The 20 cannot help even with the lightest plate: drop it.
The trap is using this on data that is not sorted. The "cannot help" argument depends entirely on the right end holding the largest value. On an unsorted list you would either sort first, which costs n log n and moves every item away from its original position, or go back to the dictionary.
Drills
Answer fast — trust the rule.
Plates [2, 5, 7, 11, 14, 20], target 18. The pointers sit on 5 and 14, total 19. What happens next?
What does sorted_pair([1, 3, 4, 6, 9], 20) return?
The total is too small. Why is it safe to drop the value at left?
Compared with the dictionary complement lookup, what does the sorted squeeze save?
Remember
- Sum too small, move left up; sum too big, move right down.
- Shortcut: compare, then drop the side that caused the miss; never go back.
- Trap: squeezing unsorted data; sort first, remembering positions, or use a dictionary.