LeetCode 881: Boats to Save People

Problem Restatement

We are given an array people, where people[i] is the weight of the ith person.

We also have an unlimited number of boats. Each boat has weight limit limit.

Each boat can carry at most two people at the same time, and their total weight must be at most limit.

Return the minimum number of boats needed to carry everyone. The official constraints allow up to 5 * 10^4 people, and each weight is at most limit.

Input and Output

Function shape:

def numRescueBoats(self, people: list[int], limit: int) -> int:
    ...

Examples

Example 1:

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

Both people can share one boat:

1 + 2 = 3

Example 2:

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

One optimal arrangement is:

So the answer is 3.

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4

No pair can fit with 5, 4, or either 3.

So each person needs a separate boat.

First Thought: Try All Pairings

A direct idea is to pair people in every possible way and choose the arrangement with the fewest boats.

But this becomes complicated quickly.

For each person, we would need to decide whether they go alone or pair with another remaining person. That kind of search has many possible combinations.

The constraints are too large for this.

We need a greedy rule that makes one safe decision at a time.

Key Insight

Sort the people by weight.

Then always consider:

The heaviest remaining person must take a boat now.

There are only two possibilities:

1. The heaviest person can share with the lightest person.
2. The heaviest person cannot share with the lightest person.

If the heaviest person cannot share with the lightest person, then they cannot share with anyone else, because everyone else is at least as heavy as the lightest person.

So the heaviest person must go alone.

If the heaviest person can share with the lightest person, we put them together. This uses one boat and removes two people.

This greedy choice is safe because the heaviest person is the hardest person to place. Pairing them with the lightest possible partner preserves heavier remaining people for later decisions.

Algorithm

Sort people.

Initialize:

left = 0
right = len(people) - 1
boats = 0

While left <= right:

1. Try to put people[left] and people[right] in the same boat.
2. If their sum is at most limit, move left rightward.
3. Always move right leftward, because the heaviest remaining person gets a boat in this step.
4. Add one boat.

Return boats.

Walkthrough

Use:

people = [3,2,2,1]
limit = 3

After sorting:

[1,2,2,3]

Answer:

3

Correctness

After sorting, people[left] is the lightest remaining person and people[right] is the heaviest remaining person.

At each step, the heaviest remaining person must be placed in some boat.

If people[left] + people[right] > limit, then the heaviest person cannot pair with the lightest remaining person. Since every other remaining person is at least as heavy as people[left], the heaviest person cannot pair with anyone. Therefore, sending the heaviest person alone is forced.

If people[left] + people[right] <= limit, then the heaviest person can share a boat with the lightest person. This uses one boat for two people. It is safe to pair them because the heaviest person is removed, and the lightest person is the least restrictive possible partner.

In both cases, the algorithm uses one boat for the heaviest remaining person in an optimal way. Then the same reasoning applies to the smaller remaining set of people.

By induction over the number of remaining people, the algorithm returns the minimum possible number of boats.

Complexity

The two-pointer scan itself is O(n).

Implementation

class Solution:
    def numRescueBoats(self, people: list[int], limit: int) -> int:
        people.sort()

        left = 0
        right = len(people) - 1
        boats = 0

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

            right -= 1
            boats += 1

        return boats

Code Explanation

We sort the weights:

people.sort()

This lets us compare the lightest and heaviest remaining people.

The two pointers start at both ends:

left = 0
right = len(people) - 1

The loop continues while at least one person remains:

while left <= right:

If the lightest and heaviest can share one boat:

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

we remove the lightest person too.

The heaviest person is always placed in a boat during this iteration:

right -= 1
boats += 1

Finally, boats contains the minimum number of boats needed.

Testing

def run_tests():
    s = Solution()

    assert s.numRescueBoats([1, 2], 3) == 1
    assert s.numRescueBoats([3, 2, 2, 1], 3) == 3
    assert s.numRescueBoats([3, 5, 3, 4], 5) == 4
    assert s.numRescueBoats([5], 5) == 1
    assert s.numRescueBoats([1, 1, 1, 1], 2) == 2
    assert s.numRescueBoats([2, 2, 2, 2], 3) == 4

    print("all tests passed")

run_tests()

Test meaning: