Watch 10 video solutions for Boats to Save People, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by NeetCode has 37,078 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two 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.
Example 1:
Input: people = [1,2], limit = 3 Output: 1 Explanation: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3 Output: 3 Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
Input: people = [3,5,3,4], limit = 5 Output: 4 Explanation: 4 boats (3), (3), (4), (5)
Constraints:
1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104Problem Overview: You are given an array people where each value represents a person's weight and a boat weight limit limit. Each boat can carry at most two people as long as their combined weight does not exceed the limit. The task is to compute the minimum number of boats required to carry everyone.
Approach 1: Greedy Pairing with Sorting (O(n log n) time, O(1) space)
The key insight is that pairing the lightest and heaviest people together minimizes wasted capacity. Start by sorting the array so weights are in ascending order using a sorting step. Then repeatedly try to pair the heaviest remaining person with the lightest person. If their combined weight fits within limit, send them together; otherwise the heaviest person must go alone. This greedy strategy works because the heaviest person cannot pair with anyone heavier, so checking the lightest possible partner is always optimal. The algorithm runs in O(n log n) time due to sorting and uses O(1) extra space if the sort is in-place.
Approach 2: Two-Pointer Optimization (O(n log n) time, O(1) space)
After sorting the array, use the classic two pointers pattern. Maintain one pointer at the start (lightest person) and another at the end (heaviest person). If people[left] + people[right] <= limit, move both pointers inward because those two can share a boat. Otherwise only move the right pointer because the heaviest person must go alone. In either case, increment the boat counter. This approach is essentially a structured greedy scan of the sorted array and guarantees that every boat is used as efficiently as possible. The scan itself is linear O(n), but sorting dominates the runtime at O(n log n). Extra space remains O(1).
This pattern is a common application of greedy algorithms. Instead of exploring all pair combinations, the algorithm always makes the locally optimal choice: place the heaviest remaining person in a boat immediately.
Recommended for interviews: The sorted two-pointer greedy approach is the expected solution. It demonstrates recognition of the greedy pairing insight and efficient use of the two-pointer pattern. A brute-force pairing approach would require checking many combinations and quickly becomes impractical. Interviewers typically look for the reasoning that the heaviest person should always be placed first and paired with the lightest feasible partner.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Pairing with Sorting | O(n log n) | O(1) | General case where people weights are unsorted |
| Two-Pointer Scan After Sorting | O(n log n) | O(1) | Best practical implementation once the array is sorted |