# Boats to Save People
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/boats-to-save-people)
Canonical: https://scaleengineer.com/dsa/problems/boats-to-save-people
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Docusign](https://scaleengineer.com/companies/docusign), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [UiPath](https://scaleengineer.com/companies/uipath), [Sigmoid](https://scaleengineer.com/companies/sigmoid)
---
## Problem
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
## Brute Force with Memoization
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.
**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.
**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).
### Explanation
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.

```java
// 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;
    }
}
```
### 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)`.

## Graph Maximum Matching
This problem can be modeled as finding a maximum matching in a graph. Each person is a vertex, and an edge exists between two vertices if the corresponding people can share a boat (their combined weight is at most `limit`). The goal is to maximize the number of pairs, as each pair uses one boat, while unpaired people use one boat each.
**Time:** O(N^2.5). Building the graph takes O(N^2). Finding maximum matching in a general graph using the blossom algorithm takes O(E * sqrt(V)), which is O(N^2 * sqrt(N)) = O(N^2.5) in the worst case. · **Space:** O(N^2) to store the graph, for instance, using an adjacency matrix or an adjacency list for a dense graph.
**Pros:** Provides a formal graph-theoretic model for the problem.; It is guaranteed to find the optimal solution.
**Cons:** The time complexity is too high for the given constraints.; Implementing an algorithm for maximum matching in a general graph (like Edmonds' blossom algorithm) is highly complex and not practical for typical programming contests.
### Explanation
The total number of boats can be expressed as `(number of pairs) + (number of single people)`. If we form `M` pairs, we use `M` boats. The remaining `N - 2*M` people must go in single boats. The total number of boats is `M + (N - 2*M) = N - M`. To minimize the total boats, we must maximize `M`, the number of pairs. This is precisely the maximum matching problem on a graph.

**Steps:**
1.  **Construct a graph:** Create a graph with `N` vertices.
2.  For every pair of people `(i, j)`, if `people[i] + people[j] <= limit`, add an edge between vertex `i` and vertex `j`.
3.  **Find Maximum Matching:** Use a standard algorithm to find the maximum matching in this general graph. Let the size of the matching be `M`.
4.  **Calculate Boats:** The minimum number of boats is `N - M`.

```java
// Note: Implementing Edmonds' blossom algorithm is highly complex and
// not expected in a typical coding interview. This is a conceptual approach.
// The code below is a placeholder to illustrate the idea.
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        // Step 1: Build the graph (conceptual)
        // An adjacency list or matrix would be created here.
        // For every pair (i, j) with people[i] + people[j] <= limit, an edge is added.

        // Step 2: Find maximum matching M
        // This requires a complex algorithm like Edmonds' blossom algorithm.
        // int M = findMaxMatching(graph, n);
        int M = 0; // Placeholder for the result of max matching

        // Step 3: Calculate result
        // return n - M;
        
        // Due to the complexity and inefficiency, this approach is not practical
        // for the given constraints.
        return -1; // Placeholder
    }
}
```
### Algorithm
*   Create a graph `G` with `N` vertices, where `N` is the number of people.
*   For `i` from 0 to `N-1`:
    *   For `j` from `i+1` to `N-1`:
        *   If `people[i] + people[j] <= limit`, add an edge between vertex `i` and vertex `j` in `G`.
*   Find the size of the maximum matching, `M`, in `G` using an algorithm like Edmonds' blossom algorithm.
*   The minimum number of boats required is `N - M`.

## Greedy Approach with Sorting and Two Pointers
The most efficient approach is a greedy one. The intuition is that to maximize pairings, we should try to pair the heaviest person with the lightest person. If they can fit in a boat, we pair them. If not, the heaviest person is too heavy to be paired with anyone else (since everyone else is heavier than or equal to the lightest person), so they must take a boat alone. This strategy guarantees an optimal solution.
**Time:** O(N log N). The dominant operation is sorting the array. The subsequent two-pointer scan takes O(N) time. · **Space:** O(log N) or O(N). This depends on the space used by the sorting algorithm's implementation. In Java, `Arrays.sort` for primitives uses a tuned quicksort which has an average space complexity of O(log N) for the recursion stack.
**Pros:** Highly efficient with a time complexity dominated by sorting.; Simple to understand and implement.; Correctly finds the minimum number of boats.
**Cons:** Requires sorting the array, which takes O(N log N) time.; The sorting step might modify the input array, which could be undesirable in some contexts. A copy can be made to avoid this, at the cost of O(N) extra space.
### Explanation
By sorting the `people` array, we can easily access the lightest and heaviest people at any time using two pointers. We use a `left` pointer for the lightest person and a `right` pointer for the heaviest.

In each step of our loop, we decide the fate of the heaviest person (`people[right]`). They must get into a boat. The best way to save boats is to see if they can share. The best candidate for sharing is the lightest available person (`people[left]`), because if the lightest person can't fit, no one else can.

- If `people[left] + people[right] <= limit`, they can share. We count one boat for this pair and advance both pointers (`left++`, `right--`).
- If `people[left] + people[right] > limit`, the heaviest person cannot be paired. They must take a boat alone. We count one boat for this person and move on to the next heaviest person (`right--`). The lightest person (`people[left]`) remains to be seated.

This process continues until the pointers cross (`left > right`), at which point everyone has been assigned a boat. The total count of boats used is the minimum required.

```java
import java.util.Arrays;

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int boats = 0;
        int left = 0;
        int right = people.length - 1;

        while (left <= right) {
            boats++;
            // The heaviest person at 'right' must take a boat.
            // Check if the lightest person at 'left' can share the boat.
            if (people[left] + people[right] <= limit) {
                left++; // Both people fit, so the lightest person is also saved.
            }
            right--; // The heaviest person is always saved in this step.
        }

        return boats;
    }
}
```
### Algorithm
*   Sort the `people` array in non-decreasing order.
*   Initialize `boats = 0`.
*   Initialize two pointers: `left = 0` (lightest person) and `right = people.length - 1` (heaviest person).
*   While `left <= right`:
    *   Increment `boats` count by 1, as we are dispatching one boat in this step.
    *   The heaviest person at `people[right]` is placed in this boat.
    *   Check if the lightest available person `people[left]` can fit with the heaviest, i.e., `people[left] + people[right] <= limit`.
    *   If they can fit, pair them up by moving the `left` pointer forward: `left++`.
    *   The heaviest person is now on a boat, so move the `right` pointer backward: `right--`.
*   Return `boats`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numRescueBoats(vector<int> &people, int limit) {
    sort(people.begin(), people.end());
    int ans = 0;
    for (int i = 0, j = people.size() - 1; i <= j; --j) {
      if (people[i] + people[j] <= limit) {
        ++i;
      }
      ++ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int: people . sort() ans = 0 i, j = 0, len(people) - 1 while i <= j: if people[i] + people[j] <= limit: i += 1 j -= 1 ans += 1 return ans

```