Boats to Save People

GREEDY · MEDIUM

The problem

You’re given an array people, where people[i] is the weight of the ith person, and an unlimited supply of boats. Each boat can carry at most limit total weight and holds at most two people at once — but only if their combined weight doesn’t exceed limit. Every person must go somewhere. Return the minimum number of boats needed to get everyone across.

LeetCode: Boats to Save People

Solution 1: Brute force — repeatedly scan for the best pairing

A natural first instinct: each round, scan every still-unassigned person to find the heaviest one (they’re the most constrained — fewest people can share a boat with them), then scan every still-unassigned person again to find the heaviest partner who still fits with them. Assign whoever was found, shrink the unassigned pool, and repeat. It’s correct, but every round pays for two full linear scans over a shrinking set.

function numRescueBoatsBrute(people, limit) {
  const n = people.length;
  const used = new Array(n).fill(false);
  let boats = 0;
  let remaining = n;

  while (remaining > 0) {
    // Scan every unassigned person to find the heaviest.
    let heavyIdx = -1;
    for (let i = 0; i < n; i++) {
      if (!used[i] && (heavyIdx === -1 || people[i] > people[heavyIdx])) heavyIdx = i;
    }
    used[heavyIdx] = true;
    remaining--;

    // Scan every remaining unassigned person for the best-fitting partner.
    let partnerIdx = -1;
    for (let i = 0; i < n; i++) {
      if (!used[i] && people[i] + people[heavyIdx] <= limit) {
        if (partnerIdx === -1 || people[i] > people[partnerIdx]) partnerIdx = i;
      }
    }
    if (partnerIdx !== -1) {
      used[partnerIdx] = true;
      remaining--;
    }
    boats++;
  }
  return boats;
}

Line by line:

The outer while loop runs once per boat — up to n times.
The first inner loop scans every unassigned person to find the heaviest — that’s the person hardest to pair, so they’re handled first each round.
The second inner loop scans every remaining unassigned person again, looking for the heaviest one that still fits alongside the person just chosen (people[i] + people[heavyIdx] <= limit).
If no partner fits, partnerIdx stays -1 and that person takes a boat alone — still one boat either way, so boats++ runs unconditionally at the bottom of the loop.

Complexity

Time	Space	Approach
O(n²)	O(n)	Two full linear scans of the shrinking unassigned set, per boat

Interactive visualization

people = [3, 2, 2, 5, 6, 1], limit = 6 — brute force traces repeated full scans

Press play to run the brute force algorithm.

boats: — · scan phase: —

Step 0 / 14

Solution 2: Optimal — sort once, two-pointer greedy

Sort everyone by weight. The heaviest person left is always the hardest to pair — so try pairing them with the lightest person left, since a lighter partner gives the pair the best possible chance of fitting under limit. If lightest + heaviest fits, send them together and advance both pointers. If it doesn’t fit, no one left is light enough to pair with the heaviest (everyone else is heavier still) — so the heaviest goes alone, and only that pointer advances. Either way, exactly one boat is used and the pointers close in on each other.

function numRescueBoatsOptimal(people, limit) {
  const sorted = people.slice().sort((a, b) => a - b);
  let lo = 0, hi = sorted.length - 1;
  let boats = 0;

  while (lo <= hi) {
    if (sorted[lo] + sorted[hi] <= limit) {
      lo++; // lightest pairs with heaviest — both board
    }
    hi--; // heaviest always leaves, paired or alone
    boats++;
  }
  return boats;
}

Line by line:

sorted[lo] + sorted[hi] <= limit is the only comparison the whole algorithm needs — the lightest and heaviest remaining people are the ONLY pairing worth checking each round (see Interview Corner for why).
If it fits, lo++ — the lightest person is now used, boarding alongside the heaviest.
hi-- runs on every iteration, no matter what — the current heaviest person is always accounted for after this round, either paired or alone.
boats++ also runs unconditionally — exactly one boat is used per iteration, whether it carries one person or two.
When lo === hi, exactly one person is left; that final iteration still adds exactly one boat and then the loop ends, so the edge case needs no special-casing.

Complexity

Time	Space	Approach
O(n log n)	O(n)	Sort once, then a single two-pointer linear pass

Interactive visualization

people = [3, 2, 2, 5, 6, 1], limit = 6 — sorted, then two-pointer greedy closes in

Press play to run the optimal two-pointer algorithm.

boats: — · pointers: —

Step 0 / 10

Complexity comparison

Solution	Time	Space
Brute force (repeated full scans)	O(n²)	O(n)
Optimal (sort + two-pointer)	O(n log n)	O(n)

Both track a “used” state per person and both correctly find the minimum boat count — they were cross-checked against each other over thousands of random inputs, not just the three LeetCode examples. The gap is entirely about how much repeated scanning it takes to find each round’s pairing: two O(n) scans per boat versus one O(n log n) sort followed by a single O(n) pass.

Interview corner

Why is it always safe to pair the lightest remaining person with the heaviest, instead of checking other pairings?

The heaviest remaining person is the hardest to pair — if they can’t fit with the lightest remaining person, they can’t fit with anyone else left either (every other remaining person is at least as heavy).
So the lightest person is literally the heaviest person’s best possible shot at sharing a boat — if that pairing fails, the heaviest person is doomed to go alone this round no matter what else is checked.
If the pairing does work, using the lightest person on the heaviest is also safe for everyone else: any lighter partner would’ve made a WORSE match for a later, still-heavy person, so nothing is lost by using them up now.

Why does the heaviest person always advance (hi--) every single iteration, paired or not?

Once the algorithm has decided what happens to the current heaviest person this round — paired with the lightest, or alone — that person is fully resolved and needs no further consideration.
The lightest person only advances (lo++) when they actually got used; if the pairing failed, they’re still unresolved and must be re-checked next round against the new heaviest.
↳ Common follow-up: “Could you ever advance lo without advancing hi?” No — every iteration retires exactly one boat and the heaviest person in it, so hi always moves; only whether lo also moves is conditional.

Would this greedy strategy still work if a boat could carry three or more people instead of two?

Not with this exact two-pointer shape — pairing “lightest + heaviest” no longer captures the best group once groups can have 3+ members.
The general k-per-boat version is a much harder combinatorial packing problem (related to bin packing), and doesn’t have a simple O(n log n) greedy solution known for arbitrary k.
The two-person cap is exactly what makes the single “check the extremes” greedy insight provably optimal here.

Trick question — what does this log?

const people = [10, 2, 33, 4];
console.log(people.sort());

Answer: [10, 2, 33, 4] — completely unsorted numerically.
Array.prototype.sort() with no comparator converts every element to a STRING and sorts lexicographically: "10" comes before "2" because "1" < "2" as characters.
people.sort((a, b) => a - b) is the fix — it forces a numeric comparison.
⚠ Trap: this is exactly why the optimal solution above writes .sort((a, b) => a - b) explicitly. Dropping the comparator wouldn’t throw an error — it would silently sort weights like [10, 2, 33, 4] into [10, 2, 33, 4] (already “sorted” as strings), and the two-pointer greedy would then compare the wrong pairs and return a wrong boat count with no crash to warn you.

Quiz

1. Why does the optimal solution only ever compare the CURRENT lightest and heaviest remaining people, instead of trying other combinations?

Any two remaining people would give the same boat count, so it doesn’t matter which pair is checked
It’s just the fastest pair to look up, not necessarily correct
The heaviest person is hardest to pair — if the lightest available person doesn’t fit with them, no one else (all heavier) will fit either

2. In while (lo <= hi) { if (fits) lo++; hi--; boats++; }, when does hi-- execute?

Every single iteration, regardless of whether the pairing fit
Only when sorted[lo] + sorted[hi] fits within the limit
Only when the pairing doesn’t fit

3. Why can’t the two-pointer scan run correctly on an unsorted people array?

Without sorting, index 0 and the last index aren’t actually the lightest and heaviest remaining people, so the greedy argument no longer applies
It works identically either way — sorting is just cosmetic
It would still be correct, just marginally slower

4. Why does boats++ run unconditionally at the bottom of the loop, instead of inside separate branches?

Every loop iteration uses exactly one boat — whether it carries one person (alone) or two (paired) — so the increment is the same either way
It’s a bug — boats should only increment when a pairing succeeds
It actually increments boats twice per successful pairing

5. What’s the time complexity difference between the two solutions, and why?

Brute force is O(n²) from two full scans per boat; optimal is O(n log n), dominated by a single sort plus one linear pass
They’re the same — O(n log n) for both
Brute force is O(n log n); optimal is O(n²)