Minimum Rescue Boats Needed Under a Weight Limit

Medium20–25 min

Topics

ArrayTwo PointerGreedySorting

Companies

AmazonGoogleMicrosoftAdobe

Every person in people needs to be ferried across, and every boat can carry at most two people at once as long as their combined weight doesn't exceed limit. Every person's own weight is guaranteed to fit within the limit on its own, so nobody is ever stranded. Find the fewest boat trips needed to get everyone across. A greedy pairing works well once the weights are sorted: try to pair the heaviest person still waiting with the lightest person still waiting. If they fit together, send both on one trip; if not, the heaviest has to go alone, since nobody lighter would fit with them either.

Test Case 1:

Input:people = [4, 6], limit = 10

Output:1

Explanation:Together they weigh exactly 10, so one boat carries them both.

Test Case 2:

Input:people = [7, 3, 5, 2], limit = 8

Output:3

Explanation:Sorted: [2, 3, 5, 7]. The lightest (2) pairs with the 5 (2+5=7 ≤ 8); the 7 goes alone; the 3 goes alone.

Test Case 3:

Input:people = [9, 9, 9], limit = 9

Output:3

Explanation:Every pair would weigh 18, over the limit, so each person needs a boat to themselves.

Constraints

◆1 ≤ people.length ≤ 5×10⁴
◆1 ≤ people[i] ≤ limit ≤ 3×10⁴
◆Every person's weight is at most limit, so everyone can always fit on some boat alone

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

people (weights) — 1-10 positive integerslimit

1	class Solution {
2	public int minimumRescueBoats(int[] people, int limit) {
3	int[] sorted = people.clone();
4	Arrays.sort(sorted);
5	int left = 0, right = sorted.length - 1;
6	int boats = 0;
7	while (left <= right) {
8	if (left < right && sorted[left] + sorted[right] <= limit) {
9	left++;
10	}
11	right--;
12	boats++;
13	}
14	return boats;
15	}
16	}
17

↑left

↑right

Variables

left0

right3

boats0

INITIALIZE

Sort the weights: [2, 3, 5, 7]. left points at the lightest person, right at the heaviest. boats starts at 0.

Step 1 / 12

Approach & Solutions

Brute Force — Rescan for a Partner

Brute

Sort the weights. Repeatedly take the heaviest person who hasn't been rescued yet, then scan everyone lighter to see if any of them still fits alongside that person within the limit — if so, rescue both together, otherwise the heaviest goes alone. Rescanning the remaining people for every boat costs O(n²) in the worst case.

TimeO(n²)

SpaceO(n)

Java

Try it out

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

Optimal — Two Pointers on Sorted Weights

Optimal

Sort the weights, then point left at the lightest person and right at the heaviest. Each round, try to send the heaviest person off with the lightest one still waiting: if they fit together, both go and left moves in; either way, the heaviest always leaves on this boat, so right always moves in. If the lightest person can't fit with the heaviest, they certainly can't fit with anyone heavier either — so the heaviest simply goes alone.

TimeO(n log n)

SpaceO(1) extra