Community Problem
Boats to Save People
Difficulty: Medium
Given person weights, a boat capacity, and a 2-person-per-boat limit, find the minimum number of boats.
Boats to Save People
Given person weights, a boat capacity, and a 2-person-per-boat limit, find the minimum number of boats.
By @chloesaeed
May 13, 2026
·
Updated May 18, 2026
179 views
4
Rate
I had this on a phone screen and the interviewer's hint was "why does pairing the heaviest with the lightest never lose?". That hint is the entire interview signal: the greedy is non-obvious because at first it looks like an ILP problem, but the exchange argument boils down to one line. The catalog covers Two Pointers but skipped this one, which is the cleanest greedy + two-pointers fusion problem in interview rotation.
Boats to Save People
You are given an array people where people[i] is the weight of the i-th person, and an integer limit (the max weight a single boat can carry). Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
Examples
Example 1:
- Input:
people = [1, 2],limit = 3 - Output:
1 - Explanation: One boat carries both.
Example 2:
- Input:
people = [3, 2, 2, 1],limit = 3 - Output:
3 - Explanation: Boat 1 carries
1 + 2, boat 2 carries2, boat 3 carries3.
Example 3:
- Input:
people = [3, 5, 3, 4],limit = 5 - Output:
4 - Explanation: No two of these weights sum to
<= 5. Every person needs their own boat.
Example 4:
- Input:
people = [5, 1, 4, 2],limit = 6 - Output:
2 - Explanation: Boat 1 carries
5 + 1, boat 2 carries4 + 2.
Constraints
1 <= people.length <= 5 * 10^4.1 <= people[i] <= limit <= 3 * 10^4.
Follow-up
Why is the greedy "pair heaviest with lightest if they fit, otherwise the heaviest goes alone" optimal? The exchange argument is short: in any optimal solution, if the heaviest person sails alone but COULD have been paired with the lightest, we can replace that solo trip with a pair without increasing the boat count.
Solution
Hints
Solution Walkthrough
Approach: Sort + Two Pointers (O(n log n) time, O(1) extra space)
The two-pointer technique on a sorted array nails this. Sort people ascending. Use i = 0 (lightest) and j = n - 1 (heaviest). At each step:
- If
people[i] + people[j] <= limit, the lightest and heaviest can share a boat. Advanceiand decrementj. - Otherwise, the heaviest cannot fit with even the lightest, so they take a boat alone. Only
jdecrements. - Either way,
boats += 1.
Loop until i > j. Return boats.
Why It Works (Exchange Argument)
Claim: pairing the heaviest with the lightest (when they fit) is never worse than any other pairing.
Suppose an optimal solution has the heaviest H traveling solo while the lightest L is paired with someone else M. We know H + L <= limit (assumption). Then in the optimal, replace the (L, M) boat and the (H,) boat with (L, H) and (M,). The boat count stays the same (or drops if M could now pair with someone else further along). So pairing H with L is at least as good.
When H + L > limit, no one can pair with H, so H must take its own boat regardless.
Complexity
Sample
Weights sorted: [1, 2, 2, 3]
i=0, j=3: 1 + 3 = 4 > limit=3 -> 3 sails alone, j=2, boats=1
i=0, j=2: 1 + 2 = 3 <= 3 -> pair, i=1, j=1, boats=2
i=1, j=1: 2 sails alone, j=0, boats=3
Loop ends.Metric Value
Time O(n log n) for the sort, O(n) for the scan
Space O(1) auxiliary (or O(n) if you keep the original array immutable)Pitfalls
- Forgetting to sort. The two-pointer logic needs sorted weights. Without sorting, pairing the FIRST and LAST elements is meaningless.
- Off-by-one on the loop. The loop condition is
i <= j. Wheni == j, that single person needs one more boat. Thej--; boats++after the body handles that without special-casing. - Trying to pack 3 or more. The boat capacity is 2 people, NOT "as many as the limit allows". A common bug is to greedily fill each boat with as many people as possible, which violates the constraint.
Solution Code