Boats to Save People — Solution in Python, Java & C++
Boats to Save People solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Boats to Save People is a medium coding problem on arrays, sorting and greedy.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Two Pointers
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given weights people and a boat weight limit. Each boat carries at most two people whose combined weight is at most limit. Every person weighs at most limit.
Return the minimum number of boats needed to carry everyone.
Example 1
Input: people = [1,2], limit = 3
Output: 1
Example 2
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: (1,2), (2), (3).
Example 3
Input: people = [3,5,3,4], limit = 5
Output: 4
Constraints
1 <= people.length <= 301 <= people[i] <= limit <= 100
Hints for Boats to Save People
Hint 1
Sort, then pair the heaviest remaining with the lightest if they fit.
Hint 2
The heaviest person leaves on every boat — the only question is whether someone joins.
How to solve Boats to Save People
The heaviest remaining person leaves on the next boat no matter what — they can never be left behind, and no one heavier exists to pair with. The only decision is whether anyone joins them, and the best companion is the lightest remaining person: if even they do not fit, nobody does.
Approach
- Sort the weights ascending.
- Put one pointer
iat the lightest person and one pointerjat the heaviest. - Launch a boat for person
j. - If
people[i] + people[j] <= limit, the lightest person rides along — advancei. - Move
jdown either way, and repeat whilei <= j.
Why it works
Pairing the heaviest with the lightest is optimal by exchange: if an optimal plan puts the heaviest with someone else — or alone while the lightest travels elsewhere — swapping in the lightest keeps every boat within the limit, since the lightest is no heavier than whoever they replace. Repeating the swap turns any optimum into this one, so greedy is never worse. And when the pair does not fit, the heaviest must sail alone in any plan, so taking that boat costs nothing.
Complexity
- Time —
O(n log n) - Space —
O(1)
Pitfalls
- The loop condition is
i <= j, noti < j— when the pointers meet, that last person still needs a boat. - Decrement
jon every iteration; a boat always carries the heaviest, whether or not it is shared. - Only advance
iwhen the pair actually fits. - Each boat holds at most two people, so a greedy "fill until full" approach is a different (and wrong) problem.
Reference solution
Python
from typing import List
def numRescueBoats(people: List[int], limit: int) -> int:
people = sorted(people)
i, j = 0, len(people) - 1
boats = 0
while i <= j:
if people[i] + people[j] <= limit:
i += 1
j -= 1
boats += 1
return boatsJava
public static int numRescueBoats(int[] people, int limit) {
int[] s = people.clone();
Arrays.sort(s);
int i = 0, j = s.length - 1, boats = 0;
while (i <= j) {
if (s[i] + s[j] <= limit) i++;
j--;
boats++;
}
return boats;
}C++
int numRescueBoats(vector<int>& people, int limit) {
vector<int> s = people;
sort(s.begin(), s.end());
int i = 0, j = (int) s.size() - 1, boats = 0;
while (i <= j) {
if (s[i] + s[j] <= limit) i++;
j--;
boats++;
}
return boats;
}JavaScript
var numRescueBoats = function(people, limit) {
const sorted = people.slice().sort(function(a, b) { return a - b; });
let i = 0, j = sorted.length - 1, boats = 0;
while (i <= j) {
if (sorted[i] + sorted[j] <= limit) i++;
j--;
boats++;
}
return boats;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms