Boats to Save People
Problem Statement
You are given an array people, where people[i] is the weight of one person, and an integer limit. Each boat can carry at most two people at the same time, as long as their combined weight is at most limit.
Return the minimum number of boats needed to carry everyone. Every person's weight is at most limit, so each person can always ride alone if necessary.
Input
An integer array people of weights and an integer limit.
Output
An integer: the minimum number of boats required to rescue everyone.
Constraints
- •
1 <= people.length <= 5 * 10^4 - •
1 <= people[i] <= limit <= 3 * 10^4 - •
Each boat carries at most two people
Examples
Example 1
people = [1,2], limit = 3
1Example 2
people = [3,2,2,1], limit = 3
3Example 3
people = [3,5,3,4], limit = 5
4Learning Objectives
- Use sorting to expose the lightest and heaviest remaining people.
- Explain why the heaviest remaining person should be assigned a boat immediately.
- Prove the safe pairing of the heaviest person with the lightest possible partner.
- Implement a two-pointer greedy loop without off-by-one errors.
Intuition
Focus on the heaviest remaining person. They must leave on the next boat in some optimal solution, either alone or with one partner. If even the lightest remaining person cannot fit with them, no one can, so sending the heaviest alone is forced.
If the lightest can fit with the heaviest, pairing them is safe. The lightest is the easiest person to pair with anyone else, but using them with the heaviest does not block a better pairing for the heaviest because every other possible partner is heavier. This gives the classic sorted two-pointer greedy: try to pair the extremes, always consume the heaviest, and use one boat per step.
Common mistakes
- ×Trying to pair the two lightest people first, which can strand heavy people unnecessarily.
- ×Moving both pointers even when the lightest does not fit with the heaviest.
- ×Forgetting that each boat can carry at most two people, not any number under the limit.
- ×Returning the number of successful pairs instead of the total number of boats.
Algorithm Explanation
Greedy strategy
Sort the weights. Keep left at the lightest remaining person and right at the heaviest remaining person. Use one boat for the heaviest person every iteration. If the lightest and heaviest fit together, put them together and move both pointers; otherwise, the heaviest rides alone and only right moves.
Why it works
The heaviest remaining person must be placed in some boat. If they cannot fit with the lightest remaining person, they cannot fit with anyone, so a solo boat is forced. If they can fit with the lightest, pairing them is safe because the lightest is the least restrictive possible partner, and the heaviest could not get a better partner that saves more than one boat.
Proof of correctness
Consider an optimal solution for the remaining people and let H be the heaviest person. If H cannot fit with the lightest person L, then H cannot fit with any remaining person, so every optimal solution gives H a solo boat, matching the greedy choice. If H can fit with L, take any optimal solution. If H already rides with L, it matches greedy. Otherwise, suppose H rides with P or alone, and L rides with Q or alone. Put H with L. If H was alone, the old boat containing L can still carry its other passenger alone if needed. If H rode with P and L was alone, then P can ride alone in L's old boat. If H rode with P and L rode with Q, then P + Q <= H + P <= limit because H is the heaviest person and H + P was valid, so P can take L's old place. In every case the boat count does not increase, creating an optimal solution matching the greedy choice. Repeating the argument proves the algorithm is optimal.
Algorithm
- Sort people in nondecreasing order.
- Set left = 0, right = people.length - 1, and boats = 0.
- While left <= right, reserve one boat for people[right].
- If people[left] + people[right] <= limit, increment left to include the lightest person in that boat.
- Always decrement right because the heaviest person has been assigned.
- Increment boats and continue until everyone is assigned.
Solutions
Solution: Sorted two pointers
After sorting, each step decides the fate of the heaviest remaining person. Pair them with the lightest remaining person if possible; otherwise send the heaviest alone.
Step-by-step
- Sort the weights in ascending order.
- Place left at the smallest weight and right at the largest weight.
- If the two weights fit within limit, move left because the lightest person shares the boat.
- Move right every iteration because the heaviest person is always assigned.
- Count one boat for each iteration and return the count.
O(n log n)
O(log n)
Sorting dominates the runtime; the two-pointer scan is linear and Java's primitive array sort uses logarithmic stack space.
Java implementation
Dry Run
Sample input
people = [3,2,2,1], limit = 3. After sorting, weights are [1,2,2,3].
| step | left index and weight | right index and weight | decision | boats used |
|---|---|---|---|---|
| 1 | 0 -> 1 | 3 -> 3 | 1 + 3 > 3, send 3 alone | 1 |
| 2 | 0 -> 1 | 2 -> 2 | 1 + 2 <= 3, pair them | 2 |
| 3 | 1 -> 2 | 1 -> 2 | only one 2 remains, send alone | 3 |
Each row assigns the heaviest remaining person. The algorithm uses three boats, which is optimal for this input.
Interview Tips
Explain why the algorithm reasons about the heaviest remaining person, not the lightest. The heaviest has the fewest pairing options, so their boat should be decided now. If a pair with the lightest fails, the solo decision is forced; if it succeeds, pairing them cannot reduce future options in a way that costs an extra boat.
Likely follow-ups
- What changes if each boat could carry up to **k** people instead of two?
- How would you solve it if the weights were already sorted?
- How would you return the actual boat assignments?
- What if there were different boat limits instead of one shared **limit**?
Similar Problems
Key Takeaways
- The heaviest remaining person is the constrained item and should be assigned immediately.
- If the lightest cannot pair with the heaviest, nobody can.
- If the lightest can pair with the heaviest, that pairing is safe by exchange.
- One two-pointer iteration always consumes the heaviest person and exactly one boat.