Fewest boats under a weight limit
people[i] is the weight of person i. Each boat carries at most two people, and their total
weight may not exceed limit. Nobody weighs more than limit. Return the smallest number
of boats that carries everyone.
Examples
| Input | Output | Why |
|---|---|---|
people = [3, 2, 2, 1], limit = 3 | 3 | Boats (1, 2), (2) and (3). |
people = [3, 5, 3, 4], limit = 5 | 4 | No two people fit together. |
Constraints
- 1 ≤ n ≤ 5 × 10⁴
- 1 ≤ people[i] ≤ limit ≤ 3 × 10⁴
Hints
Hint 1
Every boat holds one or two people, so minimising boats means maximising the number of pairs. Which person is hardest to pair?
Hint 2
The heaviest person. Who is the best partner for them, if anyone is?
Hint 3
Sort. Look at the lightest and the heaviest left. If they fit together, pair them; if not, the heaviest cannot pair with anyone and goes alone.
Where people lose marks
- Pairing the heaviest with the heaviest person who still fits. It also gives the optimum, but needs a search per step and a longer proof.
- Stopping at i < j and forgetting the last person when i = j: they need a boat too.
Dry run on [5,1,4,2,6,3],7
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5sorted10i2132435465jboats0
Sorted: 1, 2, 3, 4, 5, 6. Limit 7.
-
Step 2 / 5sorted10i2132435465jboats1
1 + 6 = 7 ≤ 7: they share boat 1.
-
Step 3 / 5sorted1021i324354j65boats2
2 + 5 = 7 ≤ 7: they share boat 2.
-
Step 4 / 5sorted102132i43j5465boats3
3 + 4 = 7 ≤ 7: they share boat 3.
-
Step 5 / 5sorted102132435465boats3
Everyone is on a boat: 3 boats.
How to think about it
Sort the weights and put i at the lightest, j at the heaviest. Each step fills
one boat with the heaviest person left:
- If
people[i] + people[j] ≤ limit, the lightest goes with them: advancei. - Either way the heaviest is now on a boat: move
jleft and count the boat.
Why pairing with the lightest is safe: if the heaviest can share with anyone, they can share with the lightest. In an optimal plan where the lightest rides with someone else, swap the lightest and the heaviest's partner (or put the lightest in with the heaviest, if the heaviest rode alone). No boat gets heavier, so the plan stays valid with the same number of boats. If the heaviest cannot share with the lightest, they cannot share at all.
Complexity. Time O(n log n) · Space O(1) beyond the sort
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def min_boats(people, limit):
p = sorted(people)
i, j, boats = 0, len(p) - 1, 0
while i <= j: # the heaviest left, p[j], takes a boat
if p[i] + p[j] <= limit: # and the lightest joins if they fit
i += 1
j -= 1
boats += 1
return boats#include <vector>
#include <algorithm>
int solve(std::vector<int> p, int limit) {
std::sort(p.begin(), p.end());
int i = 0, j = (int)p.size() - 1, boats = 0;
while (i <= j) { // the heaviest left, p[j], takes a boat
if (p[i] + p[j] <= limit) ++i; // and the lightest joins if they fit
--j;
++boats;
}
return boats;
}class Solution {
public int minBoats(int[] people, int limit) {
int[] p = people.clone();
java.util.Arrays.sort(p);
int i = 0, j = p.length - 1, boats = 0;
while (i <= j) { // the heaviest left, p[j], takes a boat
if (p[i] + p[j] <= limit) i++; // and the lightest joins if they fit
j--;
boats++;
}
return boats;
}
}function minBoats(people, limit) {
const p = people.slice().sort((a, b) => a - b);
let i = 0, j = p.length - 1, boats = 0;
while (i <= j) { // the heaviest left, p[j], takes a boat
if (p[i] + p[j] <= limit) i++; // and the lightest joins if they fit
j--;
boats++;
}
return boats;
}fn solve(people: &[i64], limit: i64) -> i64 {
let mut p = people.to_vec();
p.sort();
// i and j as a half-open window [i, j) so j never goes below zero
let (mut i, mut j, mut boats) = (0usize, p.len(), 0i64);
while i < j { // the heaviest left, p[j - 1], takes a boat
if i < j - 1 && p[i] + p[j - 1] <= limit { i += 1; }
j -= 1;
boats += 1;
}
boats
}import Data.Array
import Data.List (sort)
solve :: [Int] -> Int -> Int
solve people limit = go 0 (n - 1)
where
n = length people
p = listArray (0, n - 1) (sort people)
-- the heaviest left, p ! j, takes a boat; the lightest joins if they fit
go i j
| i > j = 0
| p ! i + p ! j <= limit = 1 + go (i + 1) (j - 1)
| otherwise = 1 + go i (j - 1)
Variants to try
- Boats that carry up to three people: the greedy argument breaks, and the problem becomes much harder (it contains bin packing).
- Weights bounded by a small limit: a counting sort makes the whole solution O(n + limit).
Next problems
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem →Write a solution and run it against the real test table.
Keep going
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.