Boats to Save People

Medium
82.

Boats to Save People

Boats to Save People is a medium coding problem on arrays, sorting and greedy.

You are given weights people and a boat weight limit. Each boat carries at most two people whose combined weight is at most limit. Every person weighs at most limit.

Return the minimum number of boats needed to carry everyone.

Example 1

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

Example 2

Input
people = [3,2,2,1], limit = 3
Output
3
Explanation
(1,2), (2), (3).

Example 3

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

Constraints

  • 1 <= people.length <= 30
  • 1 <= people[i] <= limit <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Boats to Save People — Solution in Python, Java & C++

Boats to Save People solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Boats to Save People is a medium coding problem on arrays, sorting and greedy.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, Two Pointers
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given weights people and a boat weight limit. Each boat carries at most two people whose combined weight is at most limit. Every person weighs at most limit.

Return the minimum number of boats needed to carry everyone.

Example 1

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

Example 2

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: (1,2), (2), (3).

Example 3

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

Constraints

  • 1 <= people.length <= 30
  • 1 <= people[i] <= limit <= 100

Hints for Boats to Save People

  1. Hint 1

    Sort, then pair the heaviest remaining with the lightest if they fit.

  2. Hint 2

    The heaviest person leaves on every boat — the only question is whether someone joins.

How to solve Boats to Save People

The heaviest remaining person leaves on the next boat no matter what — they can never be left behind, and no one heavier exists to pair with. The only decision is whether anyone joins them, and the best companion is the lightest remaining person: if even they do not fit, nobody does.

Approach

  1. Sort the weights ascending.
  2. Put one pointer i at the lightest person and one pointer j at the heaviest.
  3. Launch a boat for person j.
  4. If people[i] + people[j] <= limit, the lightest person rides along — advance i.
  5. Move j down either way, and repeat while i <= j.

Why it works

Pairing the heaviest with the lightest is optimal by exchange: if an optimal plan puts the heaviest with someone else — or alone while the lightest travels elsewhere — swapping in the lightest keeps every boat within the limit, since the lightest is no heavier than whoever they replace. Repeating the swap turns any optimum into this one, so greedy is never worse. And when the pair does not fit, the heaviest must sail alone in any plan, so taking that boat costs nothing.

Complexity

  • Time — O(n log n)
  • Space — O(1)

Pitfalls

  • The loop condition is i <= j, not i < j — when the pointers meet, that last person still needs a boat.
  • Decrement j on every iteration; a boat always carries the heaviest, whether or not it is shared.
  • Only advance i when the pair actually fits.
  • Each boat holds at most two people, so a greedy "fill until full" approach is a different (and wrong) problem.

Reference solution

Python

from typing import List

def numRescueBoats(people: List[int], limit: int) -> int:
    people = sorted(people)
    i, j = 0, len(people) - 1
    boats = 0
    while i <= j:
        if people[i] + people[j] <= limit:
            i += 1
        j -= 1
        boats += 1
    return boats

Java

public static int numRescueBoats(int[] people, int limit) {
    int[] s = people.clone();
    Arrays.sort(s);
    int i = 0, j = s.length - 1, boats = 0;
    while (i <= j) {
        if (s[i] + s[j] <= limit) i++;
        j--;
        boats++;
    }
    return boats;
}

C++

int numRescueBoats(vector<int>& people, int limit) {
    vector<int> s = people;
    sort(s.begin(), s.end());
    int i = 0, j = (int) s.size() - 1, boats = 0;
    while (i <= j) {
        if (s[i] + s[j] <= limit) i++;
        j--;
        boats++;
    }
    return boats;
}

JavaScript

var numRescueBoats = function(people, limit) {
    const sorted = people.slice().sort(function(a, b) { return a - b; });
    let i = 0, j = sorted.length - 1, boats = 0;
    while (i <= j) {
        if (sorted[i] + sorted[j] <= limit) i++;
        j--;
        boats++;
    }
    return boats;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms