LeetCode Problem 881

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting

Solution

LeetCode 881, Boats to Save People

Problem Understanding

This problem asks us to determine the minimum number of boats required to rescue all people, given two constraints. Each boat can carry at most two people, and the combined weight of the people in a boat cannot exceed the given weight limit.

The input consists of:

• people, an array where each value represents the weight of one person
• limit, the maximum total weight a single boat can carry

The goal is to place every person into some boat while minimizing the total number of boats used.

For example, if people = [1,2] and limit = 3, both people can share a boat because 1 + 2 = 3, which does not exceed the limit. Therefore, only one boat is needed.

The problem guarantees that every individual person's weight is less than or equal to the boat limit, so every person can always fit into a boat alone if necessary. This is important because it means there is always at least one valid solution.

The constraints are large enough that efficiency matters:

• Up to 5 * 10^4 people
• Weights and limits up to 3 * 10^4

A quadratic solution that repeatedly searches for partners for each person would likely be too slow. We need something closer to O(n log n) or better.

Several edge cases are important to think about upfront:

• Everyone may need their own boat because no pair fits within the limit.
• Every pair may fit perfectly, allowing maximal sharing.
• The array may contain many duplicate weights.
• There may be only one person.
• The heaviest person may only fit alone, which affects how we pair the remaining people.

The central challenge is finding an efficient strategy for pairing people together whenever possible without wasting boat capacity.

Approaches

Brute Force Approach

A straightforward brute force solution would repeatedly try to pair each person with another remaining person whose combined weight stays within the limit.

One possible implementation is:

1. Pick an unassigned person.
2. Search all remaining unassigned people for the heaviest valid partner.
3. Assign them to a boat.
4. Repeat until everyone is assigned.

This approach is correct because it eventually places everyone into boats while respecting the constraints. However, the repeated searching makes it inefficient.

If we search through the remaining people for every person, the time complexity becomes O(n^2). With up to 50,000 people, this can become far too slow.

Optimal Greedy Two Pointer Approach

The key insight is that sorting allows us to make optimal pairing decisions efficiently.

After sorting the weights:

• The lightest person is at the beginning.
• The heaviest person is at the end.

The heaviest person is the hardest to place because they have the fewest possible partners. Therefore, we should always process the heaviest remaining person first.

For each heaviest person:

• If they can share a boat with the lightest remaining person, we should pair them together.
• If they cannot share with the lightest person, then they cannot share with anyone else either, because everyone else is heavier.

This observation makes a greedy strategy optimal.

We use two pointers:

• left for the lightest remaining person
• right for the heaviest remaining person

At every step:

• Try pairing people[left] + people[right]
• If the pair fits, move both pointers
• Otherwise, the heaviest person goes alone, so move only right
• In both cases, one boat is used

This gives an efficient O(n log n) solution because sorting dominates the runtime.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly searches for valid partners
Optimal	O(n log n)	O(1) or O(log n) depending on sort	Sorts once, then uses greedy two pointers

Algorithm Walkthrough

1. Sort the people array in nondecreasing order.

Sorting allows us to efficiently compare the lightest and heaviest remaining people. This structure is what enables the greedy strategy. 2. Initialize two pointers.

Set:

• left = 0 for the lightest person
• right = len(people) - 1 for the heaviest person

Also initialize boats = 0. 3. Process people while left <= right.

As long as there are unassigned people, we continue assigning boats. 4. Check whether the lightest and heaviest people can share a boat.

If:

$people[left] + people[right] \le limit$

then they can ride together.

In this case:

• Increment left
• Decrement right

We successfully placed two people into one boat. 5. Otherwise, the heaviest person must go alone.

If the lightest remaining person cannot pair with the heaviest person, then nobody can pair with the heaviest person because everyone else is heavier.

So:

• Decrement right

Only the heaviest person is assigned to this boat. 6. Increment the boat count.

Every iteration uses exactly one boat. 7. Continue until all people are assigned.

When left > right, everyone has been processed. 8. Return the total number of boats.

Why it works

The correctness comes from always making the best possible placement for the heaviest remaining person.

If the heaviest person can pair with the lightest person, pairing them is optimal because it uses one boat efficiently while preserving heavier people for future pairings.

If the heaviest person cannot pair with the lightest person, they cannot pair with anyone else. Therefore, sending them alone is unavoidable and cannot be improved.

This greedy choice is always safe, which guarantees an optimal solution.

Python Solution

from typing import List

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

The implementation begins by sorting the array so that the lightest and heaviest people can be accessed efficiently using pointers.

The left pointer starts at the beginning of the array, while the right pointer starts at the end. The variable boats tracks how many boats have been used.

Inside the loop, the algorithm checks whether the lightest and heaviest remaining people can share a boat. If they can, the lightest person is paired with the heaviest person, so left moves forward.

Regardless of whether pairing succeeds, the heaviest person is always assigned to a boat during the current iteration, so right always moves backward and boats always increases by one.

The loop stops once all people have been assigned to boats.

Go Solution

package main

import "sort"

func numRescueBoats(people []int, limit int) int {
	sort.Ints(people)

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

	for left <= right {
		if people[left]+people[right] <= limit {
			left++
		}

		right--
		boats++
	}

	return boats
}

The Go implementation follows the same logic as the Python version. The primary difference is the use of sort.Ints from Go's standard library to sort the slice in place.

Go slices are reference-like structures, so sorting modifies the original slice directly. Integer overflow is not a concern here because the maximum possible sum is 60000, which easily fits within Go's int type.

The implementation naturally handles empty and single-element slices correctly, although the constraints guarantee at least one person.

Worked Examples

Example 1

Input:

people = [1,2]
limit = 3

After sorting:

[1,2]

Step	left	right	Pair Attempt	Result	Boats
1	0	1	1 + 2 = 3	Pair together	1

Final answer:

1

Example 2

Input:

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

After sorting:

[1,2,2,3]

Step	left	right	Pair Attempt	Result	Boats
1	0	3	1 + 3 = 4	3 goes alone	1
2	0	2	1 + 2 = 3	Pair together	2
3	1	1	2 alone	Single person	3

Final answer:

3

Boat assignments:

(3), (1,2), (2)

Example 3

Input:

people = [3,5,3,4]
limit = 5

After sorting:

[3,3,4,5]

Step	left	right	Pair Attempt	Result	Boats
1	0	3	3 + 5 = 8	5 goes alone	1
2	0	2	3 + 4 = 7	4 goes alone	2
3	0	1	3 + 3 = 6	One 3 goes alone	3
4	0	0	3 alone	Single person	4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on sorting implementation

The two pointer traversal itself is linear because each pointer moves only in one direction and every person is processed once.

The sorting step requires O(n log n) time, which dominates the overall complexity.

The algorithm uses only a few extra variables beyond the input array. However, the sorting implementation may use additional stack space internally, which is why some analyses report O(log n) auxiliary space.

Test Cases

from typing import List

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

sol = Solution()

assert sol.numRescueBoats([1, 2], 3) == 1  # simple pair fits exactly
assert sol.numRescueBoats([3, 2, 2, 1], 3) == 3  # mix of paired and solo boats
assert sol.numRescueBoats([3, 5, 3, 4], 5) == 4  # nobody can pair

assert sol.numRescueBoats([1], 3) == 1  # single person
assert sol.numRescueBoats([2, 2], 4) == 1  # exact limit pairing
assert sol.numRescueBoats([2, 2], 3) == 2  # pair exceeds limit

assert sol.numRescueBoats([1, 1, 1, 1], 2) == 2  # all pair perfectly
assert sol.numRescueBoats([5, 5, 5, 5], 5) == 4  # everyone must go alone

assert sol.numRescueBoats([1, 2, 3, 4, 5], 5) == 3  # mixed pairings
assert sol.numRescueBoats([1, 1, 2, 2], 3) == 2  # optimal greedy matching

assert sol.numRescueBoats([3, 2, 3, 2, 2], 6) == 3  # larger pairing combinations
assert sol.numRescueBoats([1, 2, 2, 3], 4) == 2  # multiple valid pairings

print("All test cases passed!")

Test	Why
[1,2], limit=3	Simplest successful pairing
[3,2,2,1], limit=3	Mix of paired and solo boats
[3,5,3,4], limit=5	No valid pairings
[1], limit=3	Single-element edge case
[2,2], limit=4	Exact limit pairing
[2,2], limit=3	Pair just exceeds limit
[1,1,1,1], limit=2	Every boat fully utilized
[5,5,5,5], limit=5	Everyone forced alone
[1,2,3,4,5], limit=5	General mixed scenario
[1,1,2,2], limit=3	Greedy matching validation
[3,2,3,2,2], limit=6	Multiple optimal pairings
[1,2,2,3], limit=4	Confirms pointer movement correctness

Edge Cases

Everyone Must Ride Alone

A common edge case occurs when no two people can share a boat. For example:

people = [4,4,4]
limit = 4

Each person already reaches the weight limit individually, so pairing is impossible. A buggy implementation might still attempt invalid pairings or mishandle pointer movement.

The two pointer solution handles this naturally because every pairing check fails, causing the heaviest person to be assigned alone each iteration.

Perfect Pairing Scenario

Another important case is when every boat can hold exactly two people efficiently, such as:

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

A poor greedy strategy could waste space by pairing smaller people together too early.

The sorted two pointer approach avoids this issue because it always tries to pair the heaviest remaining person first, ensuring optimal boat usage.

Single Remaining Person

Eventually, the algorithm may reach a state where only one person remains:

left == right

This can be a source of off-by-one bugs if the loop condition is incorrect.

The implementation uses:

while left <= right:

This guarantees the final unpaired person still receives a boat before the loop exits.