Leetcode 881. Boats to Save People

Problem Explanation

We are given an array, each of its element represents the weight of a person, and we are also given an integer which represents the maximum weight a boat can carry. We have to figure out the minimum number of boats required to carry all people to the destination, keeping the rule in mind that a boat can only carry two people at once assuming that the total weight of those two people does not exceed the boat's weight limit.

For instance, if the people = [3,2,1] and limit = 3 then we would need 2 boats (1,2) and (3).

Solution Approach

The problem can be solved with a two-pointer approach. The main idea is to try to maximize the capacity of each boat.

The algorithm starts by sorting the weights. Then, we initialize two pointers, i and j, to the beginning and end of the array. We decrement the number of people until the boat's weight does not exceed its limit. If the current person's weight fits in the boat, we increment the i pointer, otherwise, we just let the person with the higher weight take the boat alone.

Let's use the example for clarification [1,2,3] with a limit of 3:

• The first step will sort the array, but in this case, it's already sorted.
• Initialization: i=0 and j=2. boats=0
• The weight of the j-th person is 3 which takes an entire boat for himself. Increment boats, decrement j. Now boats=1, j=1.
• The weight of the j-th person is 2 which is less than the limit. Check if we can add the i-th person whose weight is 1. It fits in the boat so we increment i and boats, and decrement j. Now boats=2, i=1, and j=0.
• Process ends because i>j.

So, the minimum number of boats needed here is 2.

Let's see the code for this solution in various languages:

Python

1
2python
3class Solution:
4    def numRescueBoats(self, people, limit):
5        people.sort()
6        i, j = 0, len(people) - 1
7        ans = 0
8        while i <= j:
9            if people[i] + people[j] <= limit:
10                i += 1
11            j -= 1
12            ans += 1
13        return ans 

Java

1
2java
3class Solution {
4    public int numRescueBoats(int[] people, int limit) {
5        Arrays.sort(people);
6        int i = 0, j = people.length - 1;
7        int ans = 0;
8        while (i <= j) {
9            if (people[i] + people[j] <= limit)
10                i++;
11            j--;
12            ans++;
13        }
14        return ans;
15    }
16}

JavaScript

1
2javascript
3var numRescueBoats = function(people, limit) {
4    people.sort((a, b) => a - b);
5    let i = 0, j = people.length - 1;
6    let ans = 0;
7    while(i <= j) {
8        if (people[i] + people[j] <= limit)
9            i++;
10        j--;
11        ans++
12    }
13    return ans;
14};

For the C# and C++ solution, follow the same approach using the equivalent sort functions and syntax. Please note that the bulk of the algorithm lies in the sorting the array and then using a while loop with the two pointers to either pair the heaviest and lightest person or the heaviest person alone.## C#

1
2c#
3public class Solution {
4    public int NumRescueBoats(int[] people, int limit) {
5        Array.Sort(people);
6        int i = 0, j = people.Length - 1;
7        int ans = 0;
8        while (i <= j) {
9            if (people[i] + people[j] <= limit)
10                i++;
11            j--;
12            ans++;
13        }
14        return ans;
15    }
16}

C++

1
2cpp
3class Solution {
4public:
5    int numRescueBoats(vector<int>& people, int limit) {
6        sort(people.begin(), people.end());
7        int i = 0, j = people.size() - 1;
8        int ans = 0;
9        while (i <= j) {
10            if (people[i] + people[j] <= limit)
11                i++;
12            j--;
13            ans++;
14        }
15        return ans;
16    }
17};

In summary, to solve the problem, we can combine array sorting which takes O(nlogn) time complexity, with a two-pointer approach working from both ends of the sorted array resulting in O(n) time complexity. Thus the total time complexity is O(nlogn). It is important to note that this solution assumes that the boat's weight limit is at least as heavy as the heaviest person, if it's not the case, an initial validation that checks if the given weights can be located on boats of the given limit should be made.