Boats to Save People: Greedy Two Pointers

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats. Each boat can carry at most limit weight, and each boat carries at most two people at the same time. Return the minimum number of boats to carry every given person.

This is LeetCode 881: Boats to Save People, a medium-level problem that combines sorting with a greedy two-pointer strategy. The constraint that each boat holds at most two people is what makes the greedy approach clean and provably optimal.

Why this problem matters

Boats to Save People is one of the best introductions to greedy + two pointers as a combined pattern. Many two-pointer problems require you to search for an optimal pair. This one asks you to assign pairs efficiently, and the greedy rule is both intuitive and rigorous: always try to pair the lightest remaining person with the heaviest remaining person.

The "at most two people per boat" constraint is what makes the problem tractable. Without it, you would be looking at a bin-packing problem, which is NP-hard. With it, the greedy pairing strategy gives you the optimal answer in O(n log n) time.

This problem also reinforces the habit of sorting first. The moment you sort the array, the two-pointer technique becomes natural. If the lightest and heaviest fit together, they share a boat and both pointers move inward. If they do not fit, the heaviest person rides alone and only the right pointer moves. Every step removes at least one person, so the algorithm terminates quickly.

The approach: sort and greedily pair

The core idea in three steps:

1. Sort the array. This puts the lightest people on the left and the heaviest on the right.
2. Place two pointers. left starts at index 0 (lightest), right starts at the last index (heaviest).
3. Greedily pair. At each step, check if people[left] + people[right] fits within limit. If yes, both ride together and you move both pointers inward. If no, the heaviest rides alone and you move only right left. Either way, you use one boat.

Why is this optimal? Consider the heaviest person. They need a boat no matter what. The best you can do is share that boat with someone else. If even the lightest person cannot fit alongside them, then nobody can, and the heaviest rides alone. If the lightest person does fit, pairing them is the best use of that boat because the lightest person is the easiest to accommodate elsewhere, so "spending" them on this boat wastes the least capacity.

This greedy argument applies at every step. After handling the heaviest person, the next heaviest person is now at the right end, and the same logic repeats.

The solution

def numRescueBoats(people, limit):
    people.sort()
    left, right = 0, len(people) - 1
    boats = 0

    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        boats += 1

    return boats

Visual walkthrough

Let's trace the algorithm on people = [1, 2, 2, 3] with limit = 3. After sorting (the array is already sorted here), we place L at the lightest and R at the heaviest.

Notice the pattern: the heaviest person is always handled first. If they can share with the lightest, great. If not, they ride alone. Either way, one boat is used and at least one person is removed from the pool. The algorithm makes exactly one pass through the sorted array.

Complexity analysis

Sorting takes O(n log n). The two-pointer scan is O(n). Total time: O(n log n). The sort is done in-place, so no extra space beyond a few variables.

You cannot beat O(n log n) here because sorting is required. Without sorted order, there is no efficient way to know which pairs fit together.

Building blocks

This problem is built on two fundamental patterns:

Greedy pairing. When you need to pair elements optimally, sorting and then pairing from the extremes is a common strategy. The same idea appears in problems like Assign Cookies (LeetCode 455), where you match the smallest cookie to the greediest child it can satisfy, and in Minimum Number of Arrows to Burst Balloons (LeetCode 452), where you greedily group intervals.

Opposite-end convergence. Two pointers start at the ends and move inward based on a comparison. You saw this in Container With Most Water (move the shorter side) and Two Sum II (move based on sum comparison). Here, the comparison is whether the sum fits within the limit. The invariant is the same: at each step, you eliminate at least one element from consideration, and you never need to backtrack.

Edge cases to watch for

• Everyone can pair up. If every person weighs at most limit / 2, then everyone pairs and you need n / 2 boats. The algorithm handles this naturally because every left + right check succeeds.
• Nobody can pair up. If the two lightest people already exceed limit, then every person rides alone and you need n boats. The left pointer never advances, and the right pointer walks all the way down.
• Single person. One person in the array. The loop runs once, left == right, the person rides alone. Answer: 1.
• Everyone has the same weight. If all weights are w, then two people fit if 2 * w is at most limit. Otherwise every person rides alone. The algorithm handles both cases correctly.
• The lightest and heaviest barely fit. When people[left] + people[right] equals exactly limit, they pair up. The condition uses <=, not <.

From understanding to recall

The Boats to Save People solution is short: sort, two pointers, one comparison. But the reasoning behind the greedy choice is the part worth internalizing. Why is it safe to pair the lightest with the heaviest? Why does sorting make this work? Why does "at most two per boat" matter for the greedy argument?

These are exactly the kind of questions an interviewer will probe. And under time pressure, it is easy to second-guess yourself: should I try to pair heavy people together? Should I use a different data structure? The answer is no, and understanding the greedy proof is what gives you that confidence.

The opposite-end convergence and greedy pairing building blocks are small enough to drill on their own. Once you can write them from scratch and explain why they work, assembling the full solution for this problem and related ones becomes mechanical.

Related posts

• Two Sum - The foundational complement-lookup pattern that introduces pair matching
• Container With Most Water - Another opposite-end two-pointer problem with a greedy pruning argument
• 3Sum Closest - Extends the two-pointer technique with distance tracking