The “Boats to Save People” problem asks you to compute the minimum number of boats needed to rescue everyone, given an array of people’s weights and a boat weight limit. Each boat can carry at most two people at a time, and the combined weight of the people on a boat cannot exceed the limit. Your goal is to pair people in a way that uses as few boats as possible.
This problem is a classic example of a greedy strategy done right. It looks like pairing, but the key is understanding how to pair efficiently without trying every combination.
Why brute force pairing is not feasible
A naive strategy would try to test all possible pairings and choose the arrangement that uses the fewest boats. This quickly becomes computationally explosive because the number of ways to pair people grows very fast with input size.
Instead, the problem relies on a predictable structure: since each boat holds at most two people, and the only constraint is a weight limit, sorting can dramatically simplify the choices.
Sorting reveals the optimal pairing pattern
The first big insight is that once weights are sorted, the heaviest person becomes a natural anchor. The heaviest person is the hardest to place because they have the least flexibility. If they cannot be paired with someone light enough, they must go alone.
Sorting allows you to systematically decide, for each heaviest remaining person, whether they can be paired with the lightest remaining person. This is the core of the greedy strategy.
The two-pointer greedy approach
After sorting, you use two pointers: one at the start for the lightest person and one at the end for the heaviest person. At each step, you attempt to place the heaviest person on a boat. If the heaviest plus the lightest fit within the limit, you pair them together and move both pointers inward. If they do not fit, the heaviest person must go alone, and you move only the heavy pointer inward.
In either case, you have used one boat. You repeat until all people have been assigned to boats.
Why pairing heavy with light is optimal
The correctness of this greedy idea comes from a simple but powerful principle: if the heaviest person can be paired with anyone, it will be with the lightest person that still allows the boat to stay under the limit. Pairing the heaviest person with a heavier partner than necessary only reduces future options and can lead to more boats.
If the heaviest person cannot fit with the lightest person, they cannot fit with anyone else either, because everyone else is heavier than the lightest. That means sending the heaviest alone is forced, not just a greedy guess.
This forced-choice reasoning is why the two-pointer approach is both intuitive and provably correct.
Handling edge cases naturally
The two-pointer approach handles all edge cases cleanly. If only one person remains, they take one boat. If everyone is too heavy to pair, each person goes alone, and the algorithm naturally counts one boat per person. If many people can pair, the algorithm maximizes pairings without breaking constraints.
Because decisions are based on sorted order and a single inequality check, the logic stays stable and avoids complicated branching.
Time and space complexity considerations
Sorting dominates the runtime, making the solution efficient for large input sizes. The two-pointer scan is linear after sorting. Space usage depends on how sorting is performed, but the algorithm itself uses only a constant amount of extra tracking beyond the sorted list.
This is optimal in practice because the problem inherently benefits from sorted ordering.
Why this problem is popular in interviews
Boats to Save People is a popular interview question because it tests whether candidates can recognize a greedy pairing strategy and justify it correctly. Many candidates can implement the two-pointer technique, but the real evaluation is whether they can explain why it works.
It also tests whether you can spot forced decisions. The “if the heaviest can’t pair with the lightest, they can’t pair with anyone” argument is exactly the kind of reasoning interviewers look for.
What this problem teaches beyond boats
Beyond rescue boats, this problem teaches a reusable greedy template: when you must minimize the number of groups under a capacity constraint, and each group can contain at most two items, sorting plus two pointers is often the simplest optimal strategy.
If you can clearly explain why the heaviest person drives each decision, how pairing with the lightest preserves flexibility, and why failing the lightest-pair test forces a solo boat, you demonstrate strong greedy reasoning. That depth of understanding makes “Boats to Save People” an excellent exercise in sorting-driven optimization and two-pointer strategy.
If you want more coding problems explained, check out this Balanced Binary Tree coding problem solution.
Top comments (0)