Boats to Save People — Solution

Problem

You have a list of people's weights and a boat that can carry at most two people, subject to a total weight limit. Find the minimum number of boats needed so that every person gets a boat.

• Input: people = [3, 2, 2, 1], limit = 3
• Output: 3
• Explanation: The pairs (1, 2), (2), (3) use three boats — the person weighing 3 cannot share with anyone

A counter-example clarifies the pairing logic: people = [1, 2], limit = 2 needs 2 boats (1+2 > 2), not 1.

Intuition

Since each boat holds at most two people, you want to pair the heaviest remaining person with the lightest remaining person. If they fit together, great — you've used two seats on one boat. If not, the heaviest must go alone because they can't pair with anyone heavier. Sorting makes both extremes accessible at every step.

Solution — Sort and Two Pointers

Sort people by weight, then use a left pointer at the lightest end and a right pointer at the heaviest end. Every iteration, the heaviest person takes a boat; the only question is whether the lightest remaining person can join them.

1. Sort people in ascending order
2. Initialize left = 0, right = len(people) - 1, and boats = 0
3. While left <= right: check if people[left] + people[right] <= limit
4. If yes, advance left (the lightest pairs with the heaviest)
5. Always advance right and increment boats (the heaviest always departs)
6. Return boats

1def numRescueBoats(people: list[int], limit: int) -> int:
2    people.sort()
3    left, right = 0, len(people) - 1
4    boats = 0
5
6    while left <= right:
7        if people[left] + people[right] <= limit:
8            left += 1  # lightest can share a boat with the heaviest
9        right -= 1    # heaviest always takes a boat this round
10        boats += 1
11
12    return boats

Time: O(n log n) — dominated by sorting; the two-pointer scan is O(n)

Space: O(1) — only two index variables beyond the input array

Complexity Summary

Common Mistakes

• Incrementing boats only when a pair forms — every loop iteration uses exactly one boat; the only choice is whether the lightest person joins the heaviest, not whether a boat leaves
• Using left < right as the loop condition — when left == right there is exactly one person left and they still need a boat; left <= right ensures this last person is counted
• Not sorting first — the greedy works because you always compare the absolute extremes; without sorting you cannot guarantee you are testing the true lightest and heaviest remaining
• Trying to pair the heaviest with the second-heaviest — if the heaviest cannot pair with the lightest possible partner, they cannot pair with anyone heavier, so they must go alone
• Adding a special case for when people[right] > limit — the problem guarantees people[i] <= limit, meaning every person can always fit in a boat alone; no special handling is needed

Related Problems

• Two Sum II – Input Array Is Sorted — same left-and-right pointer pattern on a sorted array
• Container With Most Water — two pointers moving inward to optimize an objective
• 3Sum — extending two pointers to a three-pointer pattern on sorted input
• Squares of a Sorted Array — two pointers merging from the outer ends inward