Similar Problems

Similar Problems not available

Boats To Save People - Leetcode Solution

Companies:

LeetCode:  Boats To Save People Leetcode Solution

Difficulty: Medium

Topics: greedy sorting array two-pointers  

Problem Statement:

You are given an array people where people[i] = [weighti, limiti] and a 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.

Example 1: Input: people = [[1,2],[3,2],[4,3]], limit = 5 Output: 3 Explanation: The boatused are [1,2], [3,2], and [4,3].

Example 2: Input: people = [[3,5],[3,5],[4,3],[2,5]], limit = 5 Output: 4 Explanation: The boatused are [3,2], [3,2], [4,3], and [2,5].

Approach:

The solution to this problem can be done by using a two-pointer approach. We can start by sorting the array of people by their weight in ascending order. This is because we want to first take the lightest people in the boat.

Let's initialize two pointers, start, and end to the first and last indices of the people array respectively. We then keep moving these pointers inward towards each other. We keep taking people in boas as long as their weight summation is less than or equal to the limit. We continue this until we exhaust all the people.

In the boat, we can take two people at the most and should be equal to or greater than the weight value of each people in the boat. i.e., lightweight can be linked with only the lightweight and heavy weight can be linked with a heavyweight.

For example: people =[1,3,2,2] -> light: 1,2,2 -> 4/limit = 2,1 boats used.

Algorithm:

  1. Sort the people array by their weight in ascending order.
  2. Initialize two pointers, start and end to first and last indices of the people array respectively.
  3. Initialize variable boats to zero.
  4. Move both pointers towards each other until start <= end.
  5. If the weight of people pointed by start and end pointers is greater than the limit, then we can only take the heavy one with us in a boat, and boats count increases, end.–
  6. Else, we keep the count of both the people in the boat and move both the start and end pointers by incrementing start and decrementing end.
  7. After iterating through the whole array, we return the count of boats

Pseudo Code:

def num_rescue_boats(people: List[int], limit: int) -> int:
    # sort the people by their weights in ascending order.
    people.sort()
    # Initialize start and end pointers
    start, end = 0, len(people) - 1
    # Initialize number of boats to 0 and iterate over the people array.
    boats = 0
    while start <= end:
        # If the weight greater than limit, move end pointer
        if people[end] + people[start] > limit:
            end -= 1
        # Otherwise, increment start and decrement end pointers
        else:
            start += 1
            end -= 1
        # Increment boat on each iteration
        boats += 1
    # Return the boat count
    return boats

Time Complexity: O(n*log(n)) - for sorting where n = number of people Space Complexity: O(1) - as we are not storing any extra data.

Final Solution:

from typing import List

def num_rescue_boats(people: List[int], limit: int) -> int:
    # sort the people by their weights in ascending order.
    people.sort()
    # Initialize start and end pointers
    start, end = 0, len(people) - 1
    # Initialize number of boats to 0 and iterate over the people array.
    boats = 0
    while start <= end:
        # If the weight greater than limit, move end pointer
        if people[end] + people[start] > limit:
            end -= 1
        # Otherwise, increment start and decrement end pointers
        else:
            start += 1
            end -= 1
        # Increment boat on each iteration
        boats += 1
    # Return the boat count
    return boats

Boats To Save People Solution Code

1