LeetCode #881 Boats to Save People Solution & Explanation

LeetCode Problem

You are given an array people where people[i] is the weight of the i^th 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 * 10⁴
• 1 <= people[i] <= limit <= 3 * 10⁴

Solution

In our solution, we first sort the weights of each person. Then, we use two pointers to efficiently navigate through the array.

• If the sum of the weights of the two individuals is less than or equal to the limit, we advance both pointers.
• If the sum exceeds the limit, we only allow the person at the last current index to board the boat.

This approach ensures the minimum number of boats needed to transport all individuals.

C# Solution

Solution1 – Sort + two pointers

public class Solution {
    public int NumRescueBoats(int[] people, int limit) {
        Array.Sort(people);
        int i = 0;
        int j = people.Length-1;

        int boats = 0; //count of minimum number of boats
        

        while(i<=j){
            var num1 = people[i];
            var num2 = people[j];

            if(num1+num2<=limit){
                i+=1;
            }
            j-=1;
            boats+=1;
        }
        return boats;
    }
}

Conclusion

I personally believe that this problem shouldn’t be classified as medium difficulty. This is because each boat is limited to carrying a maximum of two people, and the weight of each person also doesn’t exceed the limit. Therefore, many complexities that need to be considered are eliminated.

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Boats to Save People – LeetCode

Similar Questions(using two pointers)

• LeetCode #3 Longest Substring Without Repeating Characters Solution & Explanation – Zyrastory
• LeetCode #88 Merge Sorted Array Solution & Explanation – Zyrastory
• LeetCode #455 Assign Cookies Solution & Explanation – Zyrastory
• LeetCode #2441 Largest Positive Integer That Exists With Its Negative Solution & Explanation – Zyrastory

Some Random LeetCode posts