Fix One, Squeeze Two: Triples That Cancel Out
An accountant has a list of adjustments, credits positive and debits negative, and wants every distinct set of three entries that cancel out to exactly zero. Trying every triple is about n³ work, which already crawls at a few thousand entries. Pairs had a fast trick; triples can reuse it.
The rule
Sort, fix each value, then squeeze the rest for what it needs.
Once one value is fixed, the other two must add up to minus that value, and "two values with a known total in a sorted list" is exactly the sorted squeeze. So: sort once, loop over each position as the fixed value, and run a squeeze on everything to its right.
def zero_triples(nums):
nums = sorted(nums)
found = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # same fixed value, same triples
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
found.append((nums[i], nums[left], nums[right]))
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1 # skip repeats of the value just used
return foundThe cost is n squeezes of up to n steps each, about n², plus the sort. Sorting does a second job for free: equal values sit side by side, so skipping duplicates is just "is this the same as the one before?" That is how the answer lists each triple once without needing a set.
Could the inner pair use the complement lookup from the hashing section instead? It could, and the total would still be about n², but it needs a fresh set for every fixed value, and keeping out repeated triples becomes much fiddlier without sorted order. The squeeze is the cleaner answer.
The shortcut
Say the reduction out loud: "a triple is one fixed value plus a pair." Every k-sum problem shrinks the same way, fixing one value at a time until only a pair is left for the squeeze.
Sort
[-4, -1, 0, 1, 1, 2, 3]. Everything below relies on this order.
A useful early exit follows from the fourth step: once the fixed value is above zero, the two values to its right are at least as big, so the loop can stop.
Drills
Answer fast — trust the rule.
About how much work does "fix one, squeeze two" do for n values?
What does zero_triples([-2, -2, 1, 1, 4]) return?
Why skip a fixed value equal to the one before it?
The fixed value is 2 and the list is sorted. Why can the loop stop there?
Remember
- Sort, fix each value, then squeeze the rest for what it needs.
- Shortcut: a triple is one fixed value plus a pair; skip repeats by comparing with the neighbour.
- Trap: forgetting to skip duplicates, which lists the same triple more than once.