Leetcode 881. Boats to Save People

Problem

Leetcode 881 - Boats to Save People

Example:

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

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

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

Approach

We can first sort the array then have 2 pointers to take greedy approach. Meaning that we take the highest weight person first and increase the count and if we can take in more people, increment left.

Visualization of the Approach:

nums = [3,5,3,4]
limit = 5

after sorting
nums = [3,3,4,5]

left = 0
right = len(nums)-1
res = 0

nums = [3,3,4,5]
        l     r
remainder = limit - people[right] = 5-5 = 0 decrement right
Since we can't have more people decrement right and increase res
res = 1

nums = [3,3,4,5]
        l   r
remainder = limit - people[right] = 5-4 = 1 decrement right
Since remainder < people[left], increase res
res = 2

nums = [3,3,4,5]
        l r
remainder = limit - people[right] = 5-3 = 2 decrement right
Since remainder < people[left], increase res
res = 3

nums = [3,3,4,5]
        lr
remainder = limit = people[right] = 5-3 = 2 decrement right
Since left is bigger than right, return res
res = 4

Thus, res = 4

Here is the Python code for the solution:

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        left, right, res = 0, len(people)-1, 0

        while left <= right:
            remain = limit - people[right]

            right -= 1
            res += 1

            if left <= right and remain >= people[left]:
                left += 1
        
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(n log n)$ since we’re sorting the array

Space Complexity: $O(1)$