Problem Statement

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.

Examples

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<sup>4</sup>

• 1 <= people[i] <= limit <= 3 * 10<sup>4</sup>

Intuition

Understanding the problem

Before diving into solving this problem, let's take a moment to understand the problem itself.

We're given an array people where people[i] is the weight of the ith person. We have an infinite number of boats. A boat can carry at most

• limit weight and

• two people

at the same time.

Given the above conditions we need find the minimum number of boats needed to carry all the people.

Approach

If you might have noticed, the sequence of people in the people array has not impact on whether they will get a boat or not. So, if we sort the array in ascending order then we can have lower weights at the starting and higher weights at the end of array. Since, we have sorted the array we can now use the two pointer approach. The two pointer approach will be like this:

• Initialize left, right = 0, len(people)-1

• Now iterate till left <= right

• We will move our pointers like this:

  • if people[left]+people[right]<=limit, then left+=1 and right-=1. This means that we can select a person from the right side of the array and another from the left side of the array, and they can both fit on the same boat because the sum of their weights is less than or equal to the limit.

  • else: right-=1. This implies that the combined weight of people[left] and people[right] exceeds the limit. As per the constraints provided, each person's weight (people[i]) is less than or equal to the limit, indicating that no individual in the array weighs more than the limit.

• At each iteration we keep increasing the number of boats, as in each iteration we're moving the pointers. This means we're allocating a boat in every iteration.

Code Solution

Python Code:

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # sort people array
        people.sort()
        # initialize left and right pointers
        left,right=0,len(people)-1
        # initialize number of boats
        boats=0
        # iterate till left<=right
        while left<=right:
            # increment boat as in each iteration we're allocating a boat
            boats+=1
            # check if left+right<=limit
            if people[left]+people[right]<=limit:
                # move left+1
                left+=1
                # move right-1
                right-=1
            else:
                # move right-1
                # this means on people[right] is on the boat
                right-=1
        # return total boats
        return boats

Time and Space Complexity

Time Complexity:

$$O(n\ logn)$$

As we're sorting the array before iterating it.

Space Complexity:

$$O(1)$$

As we're not allocating any more space.

Conclusion

This a pretty simple problem that can be use using two pointer approach.

Hope that explanation made sense and you found this blog helpful. If you've made it this far, please give it a like and drop a comment.

Happy Coding!🚀