#881

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Boats to Save People

Find the minimum number of boats required to save all people, using a two-pointer approach for efficient pairing.

Problem Statement

You are given an array people where people[i] represents the weight of the ith person, and an infinite number of boats. Each boat can carry a maximum weight of limit, and each boat can hold at most two people at once. The goal is to find the minimum number of boats required to carry all people, where the sum of the weights of the two individuals in each boat does not exceed the limit.

Return the minimum number of boats needed to transport everyone. If it's not possible to pair people optimally, you may need to carry them in separate boats.

Examples

Example 1

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

Output: 1

1 boat (1, 2)

Example 2

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

Output: 3

3 boats (1, 2), (2) and (3)

Example 3

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

Output: 4

4 boats (3), (3), (4), (5)

Constraints

1 <= people.length <= 5 * 104
1 <= people[i] <= limit <= 3 * 104

Solution Approach

Sorting and Two-pointer Technique

Start by sorting the people array. Then use two pointers: one at the beginning (lightest person) and one at the end (heaviest person). Try to pair the lightest and heaviest individuals; if their combined weight exceeds the limit, the heavier person will need their own boat. If they fit together, move both pointers inward and assign them to a boat.

Greedy Pairing

The greedy approach ensures that we are always attempting to use the available boat capacity as efficiently as possible. By pairing the heaviest person with the lightest available person, we minimize wasted boat capacity, which directly reduces the total number of boats needed.

Time and Space Optimization

Sorting the array takes O(n log n) time, and the two-pointer scan runs in O(n). This leads to an overall time complexity of O(n log n). The space complexity is O(1) if we modify the array in place, or O(n) if we use extra space for sorting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is dominated by the sorting step, O(n log n), followed by the O(n) two-pointer scan. The space complexity is O(1) if the array is sorted in place, or O(n) for additional space usage during sorting.

What Interviewers Usually Probe

The candidate shows understanding of greedy algorithms by selecting optimal pairs.
The candidate efficiently uses a two-pointer approach to minimize boats used.
The candidate handles edge cases such as when all people exceed the boat limit by themselves.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the case where no one can be paired due to extreme weight differences.
Incorrectly using a brute force approach, which results in higher time complexity than necessary.
Not properly managing edge cases where the number of people is small or where everyone has the same weight.

Follow-up variants

What if the boat can carry more than two people at a time?
How would the problem change if there is a weight range restriction for pairing?
What if some boats can carry additional weight but with a cost?

FAQ

What is the best approach for the "Boats to Save People" problem?

The best approach is a greedy algorithm using two-pointer scanning, which efficiently minimizes the number of boats required.

How do I pair people effectively in the Boats to Save People problem?

After sorting the array, use two pointers: one at the beginning and one at the end, pairing the lightest and heaviest people together as long as their total weight doesn't exceed the limit.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, followed by an O(n) two-pointer scan.

Can I solve the problem with a brute force approach?

A brute force approach would result in higher time complexity, making it less efficient. The two-pointer method is the optimal solution.

What happens if no people can be paired due to their weights?

In cases where people cannot be paired, each individual will need their own boat, increasing the total number of boats.

terminal

Solution

Solution 1: Greedy + Two Pointers

After sorting, use two pointers to point to the beginning and end of the array respectively. Each time, compare the sum of the elements pointed to by the two pointers with `limit`. If it is less than or equal to `limit`, then both pointers move one step towards the middle. Otherwise, only the right pointer moves. Accumulate the answer.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        ans = 0
        i, j = 0, len(people) - 1
        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
            j -= 1
            ans += 1
        return ans

Continue Practicing

#870 advantage shuffle #826 most profit assigning work #948 bag of tokens