Scale Engineer

Boats to Save People

Med
#0835Time: O(N * 2^N). For each of the 2^N states (masks), we might iterate up to N people to find a pair.Space: O(2^N), where N is the number of people. This is for the memoization table and the recursion stack depth.6 companies
Patterns
Two PointersGreedy
Algorithms
Sorting
Data structures
Array
Companies
AtlassianDeutsche BankDocusignWalmart Labs

Prompt

You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

 

Example 1:

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

Example 2:

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

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

 

Constraints:

  • 1 <= people.length <= 5 * 104
  • 1 <= people[i] <= limit <= 3 * 104

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores all possible ways to group people into boats. We can define a recursive function that tries to place the next available person either alone in a boat or paired with another compatible person. To avoid recomputing results for the same subset of people, we use memoization.

Algorithm

  • Define a recursive function minBoats(mask, people, limit, memo).
  • If mask represents all people saved (all bits are 1), return 0.
  • If memo contains the result for mask, return it.
  • Find the first person i not in the current mask (i-th bit is 0).
  • Calculate an initial result by assuming person i goes alone: res = 1 + minBoats(mask | (1 << i), ...).
  • Iterate j from i + 1 to n-1:
    • If person j is also not in mask and people[i] + people[j] <= limit:
      • Update res = min(res, 1 + minBoats(mask | (1 << i) | (1 << j), ...)).
  • Store res in memo for the current mask and return it.
  • The initial call to the function would be minBoats(0, people, limit, memo).

Walkthrough

We can represent the state by a bitmask, where the i-th bit is 1 if the i-th person has been assigned a boat, and 0 otherwise. The recursive function solve(mask) calculates the minimum boats needed for the people represented by the unset bits in the mask.

Base Case: If the mask has all bits set (all people are saved), we need 0 more boats.

Recursive Step:

  1. Find the first person i who is not yet saved (i-th bit is 0).
  2. Option A (Solo boat): Place person i in a boat alone. The number of boats will be 1 + solve(mask with i-th bit set).
  3. Option B (Paired boat): Iterate through all other unsaved people j. If people[i] + people[j] <= limit, we can pair them. The number of boats will be 1 + solve(mask with i-th and j-th bits set).
  4. The result for solve(mask) is the minimum of Option A and all valid possibilities from Option B.

A map or an array can be used for memoization, storing the results for each mask to avoid redundant calculations.

// This approach is not feasible due to N <= 50000.// A bitmask would require 2^50000 states.// The code is provided for conceptual understanding only.class Solution {    public int numRescueBoats(int[] people, int limit) {        Integer[] memo = new Integer[1 << people.length];        return solve(people, limit, 0, memo);    }     private int solve(int[] people, int limit, int mask, Integer[] memo) {        if (mask == (1 << people.length) - 1) {            return 0;        }        if (memo[mask] != null) {            return memo[mask];        }         int minBoats = Integer.MAX_VALUE;        int p1_idx = -1;         // Find the first person not yet on a boat        for (int i = 0; i < people.length; i++) {            if ((mask & (1 << i)) == 0) {                p1_idx = i;                break;            }        }         // Option 1: p1 goes alone        minBoats = 1 + solve(people, limit, mask | (1 << p1_idx), memo);         // Option 2: p1 pairs with someone else        for (int p2_idx = p1_idx + 1; p2_idx < people.length; p2_idx++) {            if ((mask & (1 << p2_idx)) == 0) { // if p2 is also not on a boat                if (people[p1_idx] + people[p2_idx] <= limit) {                    minBoats = Math.min(minBoats, 1 + solve(people, limit, mask | (1 << p1_idx) | (1 << p2_idx), memo));                }            }        }         memo[mask] = minBoats;        return minBoats;    }}

Complexity

Time

O(N * 2^N). For each of the 2^N states (masks), we might iterate up to N people to find a pair.

Space

O(2^N), where N is the number of people. This is for the memoization table and the recursion stack depth.

Trade-offs

Pros

  • Guaranteed to find the optimal solution for any valid input.

Cons

  • Extremely inefficient and will time out for the given constraints.

  • The space required for memoization is prohibitively large.

  • Only feasible for very small input sizes (e.g., N < 20).

Solutions

class Solution {public  int numRescueBoats(int[] people, int limit) {    Arrays.sort(people);    int ans = 0;    for (int i = 0, j = people.length - 1; i <= j; --j) {      if (people[i] + people[j] <= limit) {        ++i;      }      ++ans;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem