Leetcode 881 - Boats to Save People

Problem Description

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)

Thought Process / Intuition

Maximum no. of boats = len(people), one person one boat. First approach: Sort people, binary search from 0 to Maximum no. of boats, check if is_valid for that no. of boats, problem is is_valid function how to check in efficient run time? Second approach: Greedy solution. The greedy choice is to try and pair the heaviest remaining person with the lighest remaining person. If the sum of their weights is less than or equal to the limit, we can pair them together. Otherwise, we can pair the heaviest person with themselves. This is because the heaviest person cannot be paired with anyone else, so they must be in their own boat. We can implement this greedy choice by sorting the list of people in ascending order and using two pointers to iterate through the list from the start and end. We pair the people at the pointers together if their sum is less than or equal to the limit, and we increment the pointer at the start. We decrement the pointer at the end in each iteration. We continue this process until the pointers meet, and we return the minimum number of boats used.

Approach

1. Sort the list people in ascending order.
2. Initialize two pointers left and right to the start and end of the list, respectively.
3. Initialize a variable boats_used to store the minimum number of boats required.
4. Iterate through the list people until the pointers left and right meet.
5. If the sum of the weights of the people at the pointers left and right is less than or equal to the limit, increment the pointer left.
6. Decrement the pointer right in each iteration.
7. Increment the variable boats_used by 1 in each iteration.
8. Return the minimum number of boats required.

Solution

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

Complexity Analysis

Time complexity: $O(n log n)$

• The time complexity of the solution is $O(n)$, where $n$ is the length of the input list people.
• We sort the list people in $O(n \log n)$ time.
• We iterate through the list people once to find the minimum number of boats required.
• The overall time complexity is $O(n \log n)$.

Space complexity: $O(1)$

• The space complexity of the solution is $O(1)$.
• We use a constant amount of extra space to store the variables left, right, and boats_used.
• The space complexity is independent of the input size.

Shoutout to My Friends' Solutions on Leetcode

My Solution