Boats to Save People - Solution & Explanation
Problem Statement
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 * 104
Approach Overview
Problem 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 1: Two-pointer Approach
This approach utilizes sorting and a two-pointer technique. By sorting the array, we simplify the pairing process, always trying to pair the lightest and heaviest person possible to fit within the limit. This method is greedy because it always tries to use the lightest and heaviest pair that fits to use fewer boats.
Here, we first sort the array of people's weights. Then, using two pointers (one at the start and one at the end), we check if the lightest person (start) and the heaviest person (end) can share a boat. If they can, we move both pointers inward. If not, we move only the end pointer. We increment the boat count in each iteration. This ensures each person is considered.
Complexity
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since we're sorting in place.
Approach 2: Greedy Pairing
In this approach, we again sort the weights, but the main focus is on maximizing each boat's capacity. If the heaviest person cannot be paired with the lightest one, they solely occupy a boat.
The approach involves sorting and using a two-pointer technique. Comparing outer values ensures efficient pairing unless the limit constraint prohibits including the lighter weight, causing the heavy weight to proceed alone.
Complexity
Time Complexity: O(n log n) - Primary time usage is the sorting step. Space Complexity: O(1) when sorting in-place.
Approach 3: Greedy + Two Pointers
After sorting, use two pointers to point to the beginning and end of the array respectively. Each time, compare the sum of the elements pointed to by the two pointers with limit. If it is less than or equal to limit, then both pointers move one step towards the middle. Otherwise, only the right pointer moves. Accumulate the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array people.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-pointer Approach | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since we're sorting in place. |
| Greedy Pairing | Time Complexity: O(n log n) - Primary time usage is the sorting step. Space Complexity: O(1) when sorting in-place. |
| Greedy + Two Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Boats to Save People - Leetcode 881 - Python • NeetCode • 40,037 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Boats to Save People easy or hard?
How to solve Boats to Save People in O(n)?
Boats to Save People Python or Java solution?
What is the best approach for Boats to Save People?
Is Boats to Save People asked at Google/Amazon/Meta?
What data structure is used in Boats to Save People?
What is the time complexity of Boats to Save People?
Ready to solve this problem?
Practice Boats to Save People with our built-in code editor and test cases.
Practice on FleetCode