Boats to Save People

NeetCode: Boats to Save People · LeetCode: 881. Boats to Save People · Difficulty: Medium

You are given an array people where people[i] is the weight of the i-th person, and an infinite supply of boats that each carry at most limit in weight and at most two people. Every person's weight is at most limit. Return the minimum number of boats needed to carry everyone.

Example

Text

Input:  people = [1, 2], limit = 3          Output: 1
Input:  people = [3, 2, 2, 1], limit = 3    Output: 3
Input:  people = [3, 5, 3, 4], limit = 5    Output: 4

Brute force: pair each heavy person with the heaviest partner that fits

The heaviest person must ride in some boat. The best companion is the heaviest remaining person who still fits with them, because any lighter companion leaves a heavier person for a later boat. So: sort, then for each unassigned person from heaviest to lightest, scan downward for the heaviest unassigned person who fits, and send them off together (or alone if nobody fits). The greedy choice is correct, but the downward scan makes it quadratic.

Java

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int[] p = people.clone();
        Arrays.sort(p);
        int n = p.length;
        boolean[] used = new boolean[n];
        int boats = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            boats++;
            for (int j = i - 1; j >= 0; j--) {
                if (!used[j] && (long) p[i] + p[j] <= limit) {
                    used[j] = true;
                    break;
                }
            }
        }
        return boats;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.numRescueBoats(new int[]{1, 2}, 3));
        System.out.println(s.numRescueBoats(new int[]{3, 2, 2, 1}, 3));
        System.out.println(s.numRescueBoats(new int[]{3, 5, 3, 4}, 5));
        System.out.println(s.numRescueBoats(new int[]{}, 5));
    }
}

Output

Time: O(n^2) for the scans (sorting is O(n log n)). Space: O(n) for the sorted copy and the used array. The pair sum is computed in long so that two large weights cannot wrap around in int.

Optimal: sort and two pointers

After sorting, the heaviest person is at the right pointer r and the lightest at the left pointer l. If the lightest fits with the heaviest, they share a boat. If not, then the heaviest cannot pair with anyone (everyone else is at least as heavy as the lightest), so they go alone. Either way r is consumed and one boat is used; l advances only when it boarded. Because the lightest person is always the best possible companion, no search is needed.

Java

import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int l = 0, r = people.length - 1;
        int boats = 0;
        while (l <= r) {
            if ((long) people[l] + people[r] <= limit) {
                l++;
            }
            r--;
            boats++;
        }
        return boats;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.numRescueBoats(new int[]{1, 2}, 3));
        System.out.println(s.numRescueBoats(new int[]{3, 2, 2, 1}, 3));
        System.out.println(s.numRescueBoats(new int[]{3, 5, 3, 4}, 5));
        System.out.println(s.numRescueBoats(new int[]{}, 5));
    }
}

Output

Time: O(n log n) for the sort, then O(n) for the sweep. Space: O(1) extra: Arrays.sort sorts people in place (the sort itself may use extra memory).

int indices can go below zero, so no guard is needed: for an empty array r starts at -1 and the loop does not run. When l == r one person is left. Whether or not l advances, r drops below l, so the loop ends and exactly one boat is counted for that person.