Boats to Save People

Leetcode Daily Challenge (3rd April, 2023)

3 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/boats-to-save-people/description/

Problem Explanation with 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)

Constraints

1 <= people.length <= 5 * 104
1 <= people[i] <= limit <= 3 * 104

Intuition:-

Only 2 people can fit in a boat at a time.
So to best utilize the limit, we should pair the heaviest person with the lightest person.
If the sum of the heaviest and lightest person is greater than the limit, then the heaviest person cannot pair with anyone. So, we can send him on a boat by himself.
If the sum of the heaviest and lightest person is less than or equal to the limit, then we can send them both in the same boat.
So, we sort the array and then use 2 pointers to find the answer.

Solution:-

Sort the array.
Initialize 2 pointers i and j to 0 and n-1 respectively.
Initialize a variable boats to 0.
While i is less than or equal to j, do the following:
If the sum of the heaviest and lightest person is less than or equal to the limit, then we can send them both in the same boat. So, we increment i by 1.
We decrement j by 1 because we have sent the heaviest person in a boat by himself or with the lightest person.
We increment boats by 1 because we have sent a boat.
Return boats.

Code:-

JAVA Solution

class Solution {
    public int numRescueBoats(List<Integer> people, int limit) {
        Collections.sort(people);
        int i = 0, j = people.size() - 1;
        int boats = 0;
        while (i <= j) {
            if (people.get(j) + people.get(i) <= limit) {
                i += 1;
            }
            j -= 1;
            boats += 1;
        }
        return boats;
    }
}

Python Solution

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

Complexity Analysis:-

TIME:-

The time complexity is O(n log n), where n is the length of the people list. This is because the Collections.sort() method has a time complexity of O(n log n), and the remaining operations have a time complexity of O(n), since we are iterating over the people list once and performing constant-time operations within the while loop.

SPACE:-

The space complexity is O(1), since we are using only a constant amount of additional space to store the variables i, j, and boats. The space required for the input list is not counted in this analysis.

References:-

Two Pointers Algorithm