Boats to Save People
Given an array people where people[i] is the weight of the i-th person, and a boat weight limit (each boat carries at most 2 people), return the minimum number of boats needed.
Intuition
Each boat holds at most two people, so the best you can ever do is pair everyone up. The greedy insight is: sort by weight, then try to pair the lightest remaining person with the heaviest. If they fit together, great — you saved a boat. If they don't, the heavy person must ride alone because they can't pair with anyone lighter either. This greedy pairing is optimal because pairing a light person with anyone heavier than their current partner cannot help — it can only waste a light person who could have freed a heavier one.
Two signals: the constraint 'at most 2 per group' and a numeric capacity limit. Whenever you need to minimise groups under a capacity and each group has bounded size, sort and try to pair extremes. The lightest-with-heaviest greedy works because failing to pair with the lightest means failing to pair with anyone.
Approach
Sort people by weight
Sorting lets you reason about pairings efficiently. After sorting, you know that if the lightest person can't fit with the heaviest, nobody can fit with the heaviest. That monotonicity is what makes the greedy argument work.
Use two pointers converging from both ends
Set left at the lightest person and right at the heaviest. If people[left] + people[right] <= limit, they share a boat — advance both pointers. Otherwise, the heavy person rides alone — advance only right. Either way, one boat is used. Continue until the pointers meet.
Count boats as pointers converge
Every iteration uses exactly one boat. When left == right, the last person rides alone. When left > right, everyone is assigned. The total boat count is the number of iterations. Time is O(n log n) for the sort plus O(n) for the two-pointer sweep. Space is O(1) beyond the sort.
Solution
Common pitfalls
Forgetting to sort before using two pointers
left, right = 0, len(people) - 1 while left <= right:
people.sort() left, right = 0, len(people) - 1 while left <= right:
Without sorting, the lightest person is not at the left end. The greedy argument — 'if the lightest can't pair with the heaviest, nobody can' — relies entirely on sorted order.
Using < instead of <= in the while condition
while left < right:
while left <= right:
When left == right, one person remains unassigned. Using strict < skips them entirely, undercounting boats by one whenever an odd number of people does not all pair up.
Always advancing both pointers regardless of fit
boats += 1 left += 1 right -= 1
if people[left] + people[right] <= limit:
left += 1
right -= 1
boats += 1If the pair does not fit, only the heavy person boards alone. Advancing left too wastes the light person — they could have paired with someone slightly less heavy on the next iteration.
Edge cases
Every pair of adjacent pointers fits. The number of boats is ceil(n / 2) — pairs consume everyone.
The lightest plus the heaviest always exceeds limit, so only right advances each time. Each person gets their own boat — n boats total.
The pointers start at the same index. One boat is used in the single iteration.