Boats to Save People — Greedy Sort and Two Pointers (LC 881)

Problem Statement#

LeetCode 881 — Boats to Save People (Medium)

You are given an array people where people[i] is the weight of the i-th person, and an integer limit representing the maximum weight a boat can carry. Each boat carries at most 2 people, provided the total weight does not exceed limit. Return the minimum number of boats required.

Constraints:

• 1 <= people.length <= 5 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4
• Each person can be accommodated individually (people[i] <= limit)

Input:  people = [1, 2], limit = 3
Output: 1

Input:  people = [3, 2, 2, 1], limit = 3
Output: 3

Why This Problem Matters#

LC 881 sits at the intersection of greedy algorithms and two pointers. It appears frequently at Google and Amazon because it requires you to prove — not just guess — that a greedy strategy is optimal. The "at most 2 people per boat" constraint is the mathematical key: either two people share a boat, or one person goes alone. This binary choice is exactly what a two-pointer scan after sorting exploits.

Many candidates reach for sorting but then pair the two lightest together. That is intuitive but wrong — the heaviest person is the hardest to pair, so always attempt to pair them with the lightest. Understanding why this is optimal (not just that it is) separates strong candidates from the rest.

The pattern here — sort, then scan inward with two pointers making a greedy pairing — generalises to LC 11, LC 167, LC 1498, and any problem where the feasibility of combining two items depends on their sum against a threshold.

The Core Insight#

Sort people ascending. Use two pointers: left at the lightest person, right at the heaviest.

At each step:

• If people[left] + people[right] <= limit: they share a boat. Move both pointers inward.
• Otherwise: the heaviest cannot share with anyone lighter (if not with the lightest, with no one). They go alone. Only advance right.

In both cases one boat is used. Count until left >= right.

Why is greedy correct? The heaviest person must board some boat. The lightest is the best possible partner — if even they cannot share, no one can. So trying to pair heaviest with lightest is optimal: it never wastes a boat.

Visual Dry Run#

Input: people = [3, 2, 2, 1], limit = 3 → sorted: [1, 2, 2, 3]

Answer: 3 boats

Solution (Optimal)#

def numRescueBoats(people: list[int], limit: int) -> int:
    people.sort()
    left, right = 0, len(people) - 1
    boats = 0
 
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1   # lightest can share
        right -= 1      # heaviest always boards this round
        boats += 1
 
    return boats

var numRescueBoats = function(people, limit) {
    people.sort((a, b) => a - b);
    let left = 0, right = people.length - 1, boats = 0;
 
    while (left <= right) {
        if (people[left] + people[right] <= limit) left++;
        right--;
        boats++;
    }
    return boats;
};

Time: O(n log n) — sort dominates; two-pointer pass is O(n) Space: O(1) — in-place sort, two variables

Common Mistakes#

• Pairing people[left] with people[left+1] — pairs the two lightest, misses the hardest person (heaviest) who needs pairing first
• Forgetting to sort — the two-pointer invariant only holds on a sorted array
• Using left < right instead of left <= right — misses the final solo person when left == right
• Not incrementing boats every iteration — each iteration uses exactly one boat regardless of whether it carries one or two people
• Thinking right-- is optional — the heaviest person always boards this round; the only question is whether they share

Interview Tips#

• State the greedy invariant clearly: "I try to pair the heaviest with the lightest. If they fit, great. If not, the heaviest must go alone — no lighter partner can do better."
• Mention that the "at most 2 per boat" constraint is what makes greedy optimal; with 3+ per boat you would need DP
• The loop terminates because at least one pointer (right) advances every iteration
• This is a classic "sort first, then think" problem — always justify the sort before writing code

Follow-up Questions#

• What if each boat could hold up to 3 people? Two pointers no longer work cleanly for triplets; DP or a more complex greedy becomes necessary.
• What if boat capacity varies per boat? This becomes bin-packing, which is NP-hard in general. The "at most 2" constraint is what keeps it polynomial.
• What is the minimum possible answer? At least ceil(n/2) boats (everyone paired), at most n boats (everyone alone).
• Can you prove the greedy is correct? By exchange argument: suppose the optimal solution does not pair the heaviest with the lightest when they fit. Swap the heaviest's partner for the lightest — the cost cannot increase.

Key Takeaways#

• Sort ascending, then use two pointers (left at lightest, right at heaviest) scanning inward
• Each iteration uses exactly one boat; the heaviest person always boards that boat
• If people[left] + people[right] <= limit, both board the same boat (advance left too)
• Loop condition is left <= right — when they meet, the single remaining person takes a solo boat
• The "at most 2 per boat" constraint is the mathematical reason greedy with two pointers is provably optimal
• Time O(n log n) dominated by sort; space O(1) — no auxiliary data structure needed