Skip to main content
CodePeetCodePeet
CodePeet 250

Boats to Save People

MEDIUMProblemSolveExternal Links

Description

You are given an array people where people[i] represents the weight of the i-th person. You also have access to an unlimited number of rescue boats. However, each boat has a maximum weight capacity of limit and can carry at most two people at the same time. The total weight of the people on a single boat must not exceed limit.

Your task is to determine the minimum number of boats required to carry every person to safety.

Note the critical constraint: each boat can hold at most two people, regardless of how much spare weight capacity remains. This means you cannot pack three lightweight people into a single boat even if their combined weight is under the limit.

Examples

Example 1

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

Output: 1

Explanation: Both persons weigh 1 and 2 respectively. Since 1 + 2 = 3 ≤ 3 (the limit), they can both fit in a single boat. Only 1 boat is needed.

Example 2

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

Output: 3

Explanation: We need to pair people optimally:

  • Boat 1: persons with weights 1 and 2 (sum = 3 ≤ 3) ✓
  • Boat 2: person with weight 2 alone (cannot pair with 3 since 2 + 3 = 5 > 3)
  • Boat 3: person with weight 3 alone

Total: 3 boats.

Example 3

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

Output: 4

Explanation: No two people can share a boat because every possible pair exceeds the limit:

  • 3 + 5 = 8 > 5
  • 3 + 4 = 7 > 5
  • 3 + 3 = 6 > 5
  • 5 + 4 = 9 > 5
  • 5 + 3 = 8 > 5
  • 4 + 3 = 7 > 5

Each person must ride alone, requiring 4 boats.

Constraints

  • 1 ≤ people.length ≤ 5 × 10^4
  • 1 ≤ people[i] ≤ limit ≤ 3 × 10^4
  • Each person's weight is guaranteed to be at most limit (so every person can fit in at least one boat alone)

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is to try every possible way of pairing people and find the arrangement that uses the fewest boats.

Imagine you are a rescue coordinator with a list of people's weights. You try to assign each unassigned person to share a boat with another unassigned person (if their combined weight allows it), or you put them in a boat alone. You want to maximize pairings so that fewer boats are needed overall.

A brute force approach would be: for each person, scan through all remaining unassigned people to find someone they can share a boat with. If a valid partner is found, pair them; otherwise, the person rides alone. This greedy-scan without sorting does not guarantee optimal pairings, but it gives a starting point for understanding the problem.

Step-by-Step Explanation

Let's trace through with people = [3, 2, 2, 1], limit = 3:

Step 1: Start with all people unassigned: [3, 2, 2, 1]. Initialize boats = 0.

Step 2: Take person at index 0 (weight 3). Scan remaining unassigned people for a partner:

  • Index 1 (weight 2): 3 + 2 = 5 > 3. Cannot pair.
  • Index 2 (weight 2): 3 + 2 = 5 > 3. Cannot pair.
  • Index 3 (weight 1): 3 + 1 = 4 > 3. Cannot pair.
  • No valid partner found. Person 0 rides alone. boats = 1.

Step 3: Take person at index 1 (weight 2). Scan remaining unassigned people:

  • Index 2 (weight 2): 2 + 2 = 4 > 3. Cannot pair.
  • Index 3 (weight 1): 2 + 1 = 3 ≤ 3. Valid pair!
  • Pair persons 1 and 3 together. boats = 2.

Step 4: Take person at index 2 (weight 2). Only unassigned person left. Rides alone. boats = 3.

Step 5: All people assigned. Result: 3 boats.

Brute Force — Greedy Scan for Partners — Watch how we scan through unassigned people for each person, trying to find a valid boat partner whose combined weight stays within the limit.

Algorithm

  1. Create a boolean array assigned of size n, initialized to false
  2. Initialize boats = 0
  3. For each person i from 0 to n-1:
    • If person i is already assigned, skip
    • Scan through all remaining unassigned persons j (from i+1 to n-1):
      • If people[i] + people[j] ≤ limit, mark j as assigned and break
    • Increment boats by 1
    • Mark i as assigned
  4. Return boats

Code

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n = people.size();
        vector<bool> assigned(n, false);
        int boats = 0;
        
        for (int i = 0; i < n; i++) {
            if (assigned[i]) continue;
            
            // Try to find a partner for person i
            for (int j = i + 1; j < n; j++) {
                if (!assigned[j] && people[i] + people[j] <= limit) {
                    assigned[j] = true;
                    break;
                }
            }
            
            assigned[i] = true;
            boats++;
        }
        
        return boats;
    }
};
class Solution:
    def numRescueBoats(self, people: list[int], limit: int) -> int:
        n = len(people)
        assigned = [False] * n
        boats = 0
        
        for i in range(n):
            if assigned[i]:
                continue
            
            # Try to find a partner for person i
            for j in range(i + 1, n):
                if not assigned[j] and people[i] + people[j] <= limit:
                    assigned[j] = True
                    break
            
            assigned[i] = True
            boats += 1
        
        return boats
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        boolean[] assigned = new boolean[n];
        int boats = 0;
        
        for (int i = 0; i < n; i++) {
            if (assigned[i]) continue;
            
            // Try to find a partner for person i
            for (int j = i + 1; j < n; j++) {
                if (!assigned[j] && people[i] + people[j] <= limit) {
                    assigned[j] = true;
                    break;
                }
            }
            
            assigned[i] = true;
            boats++;
        }
        
        return boats;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n people, we potentially scan through all remaining people to find a valid partner. In the worst case (when no pairing is possible), the inner loop runs nearly n times for each outer iteration, giving us n × n = O(n²) comparisons.

Space Complexity: O(n)

We use a boolean array of size n to track which people have been assigned to boats.

Why This Approach Is Not Efficient

The brute force approach has two significant problems:

1. Time inefficiency: With n up to 5 × 10^4, an O(n²) solution performs up to 2.5 × 10^9 operations. This far exceeds the typical time limit for competitive programming and real-time systems.

2. Suboptimal pairing: Without sorting, the brute force greedily pairs the first valid partner it finds, which may not lead to the globally optimal assignment. For instance, pairing a medium-weight person with a light person wastes the light person who could have been paired with a heavier person instead.

The key insight is: to minimize boats, we should maximize the number of valid pairings. The best strategy is to pair the heaviest available person with the lightest available person. If even the lightest person cannot share a boat with the heaviest, then the heaviest person must ride alone. This greedy observation, combined with sorting, leads us to a much more efficient solution.

Optimal Approach - Sorting + Two Pointers

Intuition

Think of this problem like loading a bus with a strict two-passenger-per-seat rule and a weight limit per seat. You want to minimize the number of seats used.

The best strategy is to sort everyone by weight, then try to pair the heaviest person with the lightest person:

  • If the heaviest and lightest can share a boat (their combined weight ≤ limit), great — pair them and move both pointers inward.
  • If they cannot share a boat, the heaviest person is too heavy to pair with anyone (since the lightest person is the best possible partner for minimizing weight). The heaviest person must ride alone. Move only the heavy pointer inward.

Why does this greedy strategy work? After sorting, the lightest person is the best candidate to pair with the heaviest person because they contribute the least additional weight. If even the lightest cannot fit with the heaviest, no one can — so the heaviest must travel alone. This ensures we never waste a lightweight person on a pairing that a heavier person needed more.

By using two pointers (one at each end of the sorted array), we process each person exactly once, making the algorithm run in O(n) time after sorting.

Step-by-Step Explanation

Let's trace through with people = [3, 2, 2, 1], limit = 3:

Step 1: Sort the array: [1, 2, 2, 3]. Initialize left = 0, right = 3, boats = 0.

Step 2: Check if lightest (people[left]=1) and heaviest (people[right]=3) can share a boat.

  • Sum = 1 + 3 = 4 > 3. They cannot pair.

Step 3: The heaviest person (weight 3) must ride alone. Only move right pointer: right = 2. boats = 1.

Step 4: Check people[left]=1 and people[right]=2.

  • Sum = 1 + 2 = 3 ≤ 3. They can share a boat!

Step 5: Pair them together. Move both pointers: left = 1, right = 1. boats = 2.

Step 6: Now left == right, meaning one person remains (people[1]=2). They ride alone. boats = 3.

Step 7: left > right, loop ends. Result: 3 boats.

Two Pointers — Pairing Lightest with Heaviest — After sorting, two pointers converge from both ends. The heaviest person either pairs with the lightest (if weight allows) or rides alone.

Algorithm

  1. Sort the people array in ascending order
  2. Initialize two pointers: left = 0 (lightest) and right = n - 1 (heaviest)
  3. Initialize boats = 0
  4. While left ≤ right:
    • If people[left] + people[right] ≤ limit:
      • Both can share a boat. Increment left (lightest person is now assigned)
    • Decrement right (heaviest person always gets a boat, alone or paired)
    • Increment boats
  5. Return boats

Code

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        
        int left = 0, right = people.size() - 1;
        int boats = 0;
        
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            boats++;
        }
        
        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:
            if people[left] + people[right] <= limit:
                left += 1
            right -= 1
            boats += 1
        
        return boats
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        
        int left = 0, right = people.length - 1;
        int boats = 0;
        
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            boats++;
        }
        
        return boats;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the array takes O(n log n). The two-pointer traversal runs in O(n) since each pointer moves at most n times total (left moves right, right moves left, and they meet in the middle). The dominant term is the sort: O(n log n).

Space Complexity: O(1) (ignoring the space used by the sorting algorithm)

We only use a constant number of variables (left, right, boats). The sorting is done in-place. Some sorting implementations may use O(log n) stack space for recursion, but no additional data structures proportional to n are created.