# Boats to Save People

### **Problem Statement:-**

You are given an array `people` where `people[i]` is the weight of the `i<sup>th</sup>` 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*.

**Link:** [https://leetcode.com/problems/boats-to-save-people/description/](https://leetcode.com/problems/boats-to-save-people/description/)

### **Problem Explanation with examples:-**

**Example 1**

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

**Example 2**

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

**Example 3**

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

**Constraints**

* `1 <= people.length <= 5 * 10<sup>4</sup>`
    
* `1 <= people[i] <= limit <= 3 * 10<sup>4</sup>`
    

### Intuition:-

* Only 2 people can fit in a boat at a time.
    
* So to best utilize the limit, we should pair the heaviest person with the lightest person.
    
* If the sum of the heaviest and lightest person is greater than the limit, then the heaviest person cannot pair with anyone. So, we can send him on a boat by himself.
    
* If the sum of the heaviest and lightest person is less than or equal to the limit, then we can send them both in the same boat.
    
* So, we sort the array and then use 2 pointers to find the answer.
    

### Solution:-

* Sort the array.
    
* Initialize 2 pointers i and j to 0 and n-1 respectively.
    
* Initialize a variable boats to 0.
    
* While i is less than or equal to j, do the following:
    
* If the sum of the heaviest and lightest person is less than or equal to the limit, then we can send them both in the same boat. So, we increment i by 1.
    
* We decrement j by 1 because we have sent the heaviest person in a boat by himself or with the lightest person.
    
* We increment boats by 1 because we have sent a boat.
    
* Return boats.
    

### Code:-

JAVA Solution

```java
class Solution {
    public int numRescueBoats(List<Integer> people, int limit) {
        Collections.sort(people);
        int i = 0, j = people.size() - 1;
        int boats = 0;
        while (i <= j) {
            if (people.get(j) + people.get(i) <= limit) {
                i += 1;
            }
            j -= 1;
            boats += 1;
        }
        return boats;
    }
}
```

Python Solution

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

### Complexity Analysis:-

**TIME**:-

The time complexity is **O(n log n)**, where n is the length of the `people` list. This is because the `Collections.sort()` method has a time complexity of O(n log n), and the remaining operations have a time complexity of O(n), since we are iterating over the `people` list once and performing constant-time operations within the while loop.

**SPACE**:-

The space complexity is **O(1)**, since we are using only a constant amount of additional space to store the variables `i`, `j`, and `boats`. The space required for the input list is not counted in this analysis.

### References:-

* [**Two Pointers Algorithm**](https://www.geeksforgeeks.org/two-pointers-technique/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)