Boats to Save People

Problem Description

You are given an array people where people[i] is the weight of the i-th person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Examples

Constraints

• 1 <= people.length <= 5 * 10⁴
• 1 <= people[i] <= limit <= 3 * 10⁴

Pairing Heaviest with Lightest Greedily

To minimize the number of boats, we should pair the heaviest person possible with the lightest person possible on the same boat. We sort the array. Place a left pointer at the lightest person and a right pointer at the heaviest person. If their combined weight people[left] + people[right] is less than or equal to the limit, they can share a boat; we increment left. Regardless of whether they can share, the heaviest person (right) must take a boat, so we decrement right and increment our boat count. We repeat this until everyone has been assigned to a boat.

Solution 1: Sorted Two-Pointer Pairing

Sort the array and pair elements from the ends to minimize boats.

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int boats = 0;

        while (left <= right) {
            boats++;
            if (left == right) {
                break; // only one person remains
            }
            if (people[left] + people[right] <= limit) {
                left++; // light person joins
            }
            right--; // heavy person leaves in their own boat
        }
        return boats;
    }
}

class Solution:
    def numRescueBoats(self, people: list[int], limit: int) -> int:
        people.sort()
        left, right = 0, len(people) - 1
        boats = 0
        
        while left <= right:
            boats += 1
            if left == right:
                break
            if people[left] + people[right] <= limit:
                left += 1  # pair successful, move lightest pointer
            right -= 1     # heaviest person takes the boat
            
        return boats

#include <vector>
#include <algorithm>

class Solution {
public:
    int numRescueBoats(std::vector<int>& people, int limit) {
        std::sort(people.begin(), people.end());
        int left = 0;
        int right = people.size() - 1;
        int boats = 0;

        while (left <= right) {
            boats++;
            if (left == right) {
                break;
            }
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
        }
        return boats;
    }
};

Complexity Analysis

• Time Complexity: O(n log n) due to the sorting step. The subsequent two-pointer scan takes O(n) time.
• Space Complexity: O(log n) or O(n) depending on the sorting implementation.

Where It Breaks

If each boat can carry more than two people, this simple two-pointer pairing approach fails. Under those conditions, the problem becomes equivalent to the Bin Packing Problem, which is NP-hard.

Common Mistakes

• Incorrect pointer movement: Decrementing both pointers regardless of weight sum. If the sum exceeds the limit, the lightest person must wait for another boat.
• Not handling the single-person base case: Allowing the loop to crash when left == right by attempting to pair the person with themselves.

Frequently Asked Questions

Why does the greedy choice work? The heaviest person must go on a boat. To optimize that boat’s capacity, the best candidate to join is the lightest person remaining. If even the lightest person cannot fit, the heaviest person must go alone.

Can we solve this using counting sort? Yes. Since the weights are bounded by the limit (people[i] <= 3 * 10^4), we can use bucket sort to sort the people in O(n + limit) time, achieving linear runtime.

← All Problems