Boats to Save People

LeetCode 881: Boats to Save People Solution & Explanation

Problem Overview

TL;DR: Sort the weights and use a two-pointer approach to pair the heaviest person with the lightest person whenever possible to minimize the total number of boats.

The Boats to Save People problem on LeetCode requires us to transport a group of people using the minimum number of boats. We are given an array of weights representing people and a weight limit for each boat. The crucial constraints are that each boat can carry at most two people at once, and the combined weight of these two people must not exceed the specified limit.

This is a classic optimization problem found in interviews, often categorized as a greedy algorithm problem. The goal of the LeetCode 881 solution is to efficiently pair individuals to maximize the utility of each boat.

Brute Force Approach for Boats to Save People

A naive approach to solving this problem would involve checking every possible combination of pairings to find the global minimum. This is essentially a partition problem where we try to group elements into the smallest number of subsets such that each subset has a size of at most 2 and a sum less than or equal to limit.

One might attempt a recursive backtracking solution:

1. Select the first remaining person.
2. Try placing them alone in a boat.
3. Try pairing them with every other remaining person (if valid).
4. Recurse for the remaining people.
5. Return the minimum boat count found among all branches.

Pseudo-code for Brute Force:

function solve(remaining_people):
    if remaining_people is empty: return 0
    min_boats = infinity
    
    person = remaining_people[0]
    
    # Option 1: Person goes alone
    min_boats = min(min_boats, 1 + solve(remaining_people - {person}))
    
    # Option 2: Person pairs with someone else
    for other in remaining_people[1:]:
        if person + other <= limit:
            min_boats = min(min_boats, 1 + solve(remaining_people - {person, other}))
            
    return min_boats

Why this fails: The time complexity of this approach approaches $O(N!)$ in the worst case because of the combinatorial branching. Given the constraint $N \le 50,000$, a factorial solution is computationally impossible and will immediately result in a Time Limit Exceeded (TLE) error. We need a solution closer to $O(N \log N)$ or $O(N)$.

Algorithm Strategy: Two Pointer Patterns

1. Sort: Sort the people array in ascending order. This transforms the data into a structure where we can access the lightest and heaviest remaining individuals in $O(1)$ time.
2. Initialize Pointers: Set left to 0 and right to people.length - 1.
3. Initialize Counter: Start a variable boats at 0.
4. Iterate: Loop while left <= right:
   • Check if people[left] + people[right] <= limit.
   • If true, it means the pair fits. Increment left (lightest person is processed).
   • Regardless of the condition, the heaviest person (people[right]) is always processed (either paired or alone). Decrement right.
   • Increment boats.
5. Return: The final value of boats.

Execution Flow

Consider people = [3, 2, 2, 1] and limit = 3.

1. Sort: The array becomes [1, 2, 2, 3].
2. Init: left = 0 (value 1), right = 3 (value 3), boats = 0.
3. Step 1:
   • Compare people[0] (1) + people[3] (3) = 4.
   • $4 > 3$ (Limit). The pair does not fit.
   • The heaviest person (3) goes alone.
   • Update: right moves to 2. left stays at 0. boats becomes 1.
4. Step 2:
   • Compare people[0] (1) + people[2] (2) = 3.
   • $3 \le 3$ (Limit). The pair fits.
   • Update: left moves to 1, right moves to 1. boats becomes 2.
5. Step 3:
   • Now left (1) == right (1). This points to the remaining person (value 2).
   • The loop condition left <= right is true.
   • Technically people[1] + people[1] is not the check logic for a single person; the logic handles the pair check. Since left == right, we can treat it as the person going alone, or simply ensure the loop handles the last element.
   • In our logic: people[left] + people[right] would be doubling the person, which is incorrect. However, usually, the logic implies checking distinct indices or handling the equality case.
   • Correction for equality: When left == right, there is only one person left. They take a boat. We increment boats and break.
   • Update: boats becomes 3.
6. Result: Return 3.

Proof of Correctness

We can prove this greedy strategy works via an exchange argument.

Let $H$ be the heaviest person and $L$ be the lightest. Suppose there is an optimal solution $S_{opt}$ that does not pair $H$ with $L$, even though $H+L \le limit$.

1. Case 1: $H$ is alone in $S_{opt}$. Since $H+L \le limit$, we can move $L$ from their boat in $S_{opt}$ to $H$'s boat. This reduces the capacity used in $L$'s original boat (potentially freeing it up entirely) without increasing the number of boats. The new solution is at least as good as $S_{opt}$.
2. Case 2: $H$ is paired with someone else, $P$, in $S_{opt}$. Since the array is sorted, $L \le P$. If $H+P \le limit$, then certainly $H+L \le limit$. We can swap $L$ and $P$. $H$ is now with $L$. $P$ takes $L$'s old spot. Since $L \le P$, the new weight in $L$'s old spot might increase, but since we are just swapping partners, the number of boats remains unchanged.

Thus, the greedy choice of pairing the heaviest with the lightest never prevents us from reaching an optimal solution.

Pattern Reuse Notes

The Two Pointers - Converging pattern used here is highly versatile. It is typically applied when we need to find pairs in a sorted array that satisfy a specific numerical condition.

• LeetCode 11: Container With Most Water: Uses converging pointers to maximize area. The decision to move pointers is based on height constraints rather than sum.
• LeetCode 15: 3Sum: Reduces the 3-element sum problem to a 2-element sum problem (Target Sum) by fixing one number and using converging pointers for the rest.
• LeetCode 16: 3Sum Closest: Similar to 3Sum, but tracks the minimum difference from a target rather than an exact match.
• LeetCode 18: 4Sum: An extension of 3Sum that uses nested loops combined with the converging pointers pattern.

Reference Implementation

C++ Solution for LeetCode 881

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int numRescueBoats(std::vector<int>& people, int limit) {
7        // Sort the people by weight to enable the two-pointer strategy
8        std::sort(people.begin(), people.end());
9        
10        int left = 0;
11        int right = people.size() - 1;
12        int boats = 0;
13        
14        while (left <= right) {
15            // Check if the lightest and heaviest person can share a boat
16            if (people[left] + people[right] <= limit) {
17                left++; // Lightest person is included
18            }
19            // Heaviest person is always included (either shared or alone)
20            right--; 
21            boats++;
22        }
23        
24        return boats;
25    }
26};

Java Solution for LeetCode 881

1import java.util.Arrays;
2
3class Solution {
4    public int numRescueBoats(int[] people, int limit) {
5        // Sort the array to use two pointers
6        Arrays.sort(people);
7        
8        int left = 0;
9        int right = people.length - 1;
10        int boats = 0;
11        
12        while (left <= right) {
13            // If the lightest person fits with the heaviest, pair them
14            if (people[left] + people[right] <= limit) {
15                left++;
16            }
17            // The heaviest person always gets on a boat
18            right--;
19            boats++;
20        }
21        
22        return boats;
23    }
24}

Python Solution for LeetCode 881

1class Solution:
2    def numRescueBoats(self, people: list[int], limit: int) -> int:
3        # Sort weights to apply greedy two-pointer logic
4        people.sort()
5        
6        left = 0
7        right = len(people) - 1
8        boats = 0
9        
10        while left <= right:
11            # Check if the lightest person can accompany the heaviest
12            if people[left] + people[right] <= limit:
13                left += 1
14            
15            # Heaviest person always takes a seat
16            right -= 1
17            boats += 1
18            
19        return boats