Problem of The Day: Boats to Save People

Problem Statement

Stack Approach - TLE

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        res = 0
        while people:
            curr_weight = people.pop()
            num_of_people = 1
            stack = []
            while people and curr_weight < limit and num_of_people < 3:
                weight = people.pop()
                if curr_weight + weight <= limit:
                    break
                stack.append(weight)

            while stack:
                people.append(stack.pop())

            res += 1

        return res

Intuition

I’m thinking about sorting the people by their weights since we want to minimize the number of boats needed. Then, I can iterate through the sorted list with two pointers, one at the beginning and one at the end, representing the heaviest and lightest people respectively.

Approach (Two pointers)

I’ll start by sorting the list of people. Then, I’ll initialize a variable to keep track of the number of boats needed. Using two pointers, I’ll iterate through the sorted list from both ends. For each iteration, I’ll check if the sum of the weights of the current heaviest and lightest person is within the limit. If it is, I’ll move the lighter person pointer towards the heavier one. Regardless, I’ll increment the boat count, as at least one person (the heaviest) will always be on the boat.

Complexity

• Time complexity: O(nlogn) due to sorting

• Space complexity: O(1)

Code

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

        return res

Editorial Solution

Approach 1: Greedy (Two Pointer)

class Solution(object):
    def numRescueBoats(self, people, limit):
        people.sort()
        i, j = 0, len(people) - 1
        ans = 0
        while i <= j:
            ans += 1
            if people[i] + people[j] <= limit:
                i += 1
            j -= 1
        return ans

• Time: O(nlogn)
• Space: O(logn)