Boats to Save People
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.
- 1 <= people.length <= 5 * 10⁴
- 1 <= people[i] <= limit <= 3 * 10⁴
Intuition
Boats to save people finds the fewest boats needed, where each boat carries at most two people and has a weight limit. The two-person cap is what makes a greedy solution both possible and provably optimal.
Sorting by weight turns the problem into a two-pointer scan. Consider the heaviest remaining person. They must travel, and the only question is whether anyone can accompany them. The best possible companion is the lightest remaining person — if that pairing fails, no other pairing can succeed:
- Pair the heaviest with the lightest when their combined weight fits; otherwise the heaviest travels alone.
That is the entire argument for optimality. Since the heaviest person cannot be avoided and the lightest is their best chance at sharing, taking that pairing whenever it fits never loses anything.
The implementation is two pointers converging from the ends of the sorted array. If people[left] + people[right] <= limit, both board and both pointers move. Otherwise only right moves, as the heaviest person sails alone. Either way a boat is counted.
One subtlety: the boat is counted on every iteration, whether one or two people boarded. Counting only on successful pairings undercounts badly.
The loop condition must be left <= right, not left < right. With an odd number of people the pointers meet on a single remaining person, who still needs a boat — using < drops them silently.
The two-person cap is essential. With three or more per boat this greedy breaks down, and the problem becomes bin packing, which is NP-hard.
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
Before reading on: price up what sorting first costs here, then ask what makes it safe to discard one end without checking it against everything. Aim for O(n log n) time and O(1) space.
Sort by weight
Sorting enables the two-pointer scan and makes "lightest" and "heaviest" available in O(1). The greedy argument depends entirely on the sorted order.
Reason from the heaviest person
The heaviest remaining person must travel, so the only question is who joins them. Their best possible companion is the lightest remaining person — if that fails, no pairing works.
Converge two pointers
Place left at the lightest and right at the heaviest. If people[left] + people[right] <= limit, both board and both pointers move; otherwise only right moves.
Count a boat every iteration
Increment the count on each iteration, whether one or two people boarded. Counting only successful pairings undercounts every solo trip.
Use the inclusive loop condition
Loop while left <= right. With an odd number of people the pointers meet on one remaining person who still needs a boat — < drops them silently.
Note where the greedy breaks
The two-person cap is essential. With three or more per boat this reasoning fails and the problem becomes bin packing, which is NP-hard.
Cost of the approach
Sorting dominates at O(n log n) time, with the scan itself O(n). Space is O(1) beyond the sort, since only two indices and a counter are held.
Solution & live demo
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.