[Two Pointers] LC 881. Boats to Save People

Goal

• Given an array people where people[i] is the weight of the ith person, and an infinite number of boats
• Each boat carries at most two people at the same time
• Return the minimum number of boats to carry every given person.

Strategy

• Set the left = 0, and right = n-1
• The right pointer is moving at a constant speed: 1 to the left every iteration, given the fact that our worst case scenario is using exactly n boats
• We are moving the left pointer to break the constant speed → while left < right, and decrease the number of boat used
• A greedy approach by adding up the largest & smallest element

Highlight

• A type of pointer problem with left and right moving toward the opposite direction
• Strong hint of using greedy

Code

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        
        l, r = 0, len(people)-1
        res=0
        
        while l<=r:
            res+=1
            if people[l] + people[r] <=limit:
                l+=1
            r-=1
        return res