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:
- Sort the people array by their weight in ascending order.
- Initialize two pointers, start and end to first and last indices of the people array respectively.
- Initialize variable boats to zero.
- Move both pointers towards each other until start <= end.
- 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.–
- 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.
- 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