LeetCode — Boats to Save People

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

Photo by Anthony Cantin on Unsplash

Problem Description: The i-th person has a weight people[i], and each boat can carry a maximum weight of limit.
Each boat carries at most 2 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. (It is guaranteed each person can be carried by boat.)

Approach Used: Sorting, Traversal

Explanation: Since it is mentioned in problem constraints that the weight of any person will not cross the boat limit. We know that there can be 2 scenarios. Either one person will travel alone in a boat or two people will travel in one boat. So in each iteration, the number of people will either get reduced by 1 or by 2 based on the above condition until all people get a seat.
If the heaviest person’s weight alone is equal to the limit then definitely he will require a separate boat. Apart from that, the most optimized case will be formed when the heaviest person available rides with lightest person available if they both meet the condition. If they cross the limit, then it is clear that heaviest person will have to travel alone because if he can’t travel with the lightest person, he can’t travel with anyone else also. If he can, then the number of people will be reduced by 2 and one people from both ends will be removed.

Code: (Java)

public int numRescueBoats(int[] people, int limit) {
        //sort the array
        Arrays.sort(people);
        
        //total number of people (always helps in referring to heaviest person at given time)
        int numberOfPeople = people.length;
        //to be calculated
        int numberOfBoats=0;
        
        for(int i=0; i<numberOfPeople; i++){
            //until we exit out of loop, there are passengers left
            //and hence one boat will be used in every iteration
            //whether it carries 1 passenger or 2
            numberOfBoats++;
            
            //if only 1 passenger was left, then abive statement added a boat for the passenger
            //we can now break out of the loop
            if(i==numberOfPeople-1)
                break;
            
            //find the totalWeight of heaviest passenger and lightest passenger
            int totalWeight = people[numberOfPeople-1]+people[i];
            
            //if last passenger has the weight equal to limit, then he will go alone
            //or if their total weight exceed limit,
            //then also only rightmost person will travel
            // we readjust i, because in next iteration i will increment
            //which means leftmost passenger also got the boat
            
            if(people[numberOfPeople-1]==limit || totalWeight>limit)
                i--;
            
            //rightmost person will always get a boat, so size will always decrease by 1
            //if leftmost person also travels, then i++ will take care of that
            numberOfPeople--;
        }
        
        //return the total number of boats needed
        return numberOfBoats;
    }

Code — with while loop for further understanding

public int numRescueBoats(int[] people, int limit) {
        //sort the array
        //to get lightest person always on leftmost index and heaviest always on rightmost index
        Arrays.sort(people);
        
        //total number of people (always helps in referring to heaviest person at given time)
        int numberOfPeople = people.length;
        
        //to be calculated
        int numberOfBoats=0;
        int startingPerson=0;
        
        while(startingPerson<numberOfPeople){
            //until we exit out of loop, there are passengers left
            //and hence one boat will be used in every iteration
            //whether it carries 1 passenger or 2
            numberOfBoats++;
            
            //if only 1 passenger was left, then above statement added a boat for the passenger
            //we can now break out of the loop
            if(startingPerson==numberOfPeople-1)
                break;
            
            //find the totalWeight of heaviest passenger and lightest passenger
            int totalWeight = people[numberOfPeople-1]+people[startingPerson];
            
            //if last passenger has the weight equal to limit, then he will go alone
            //or if their total weight exceed limit,
            //otherwise we include the first person, and increment starting person to next
            if(people[numberOfPeople-1]!=limit && totalWeight<=limit){
                startingPerson++;
            }
            
            //rightmost person will always get a boat, so size will always decrease by 1
            //if leftmost person also travels, then i++ will take care of that
            numberOfPeople--;
        }
        
        //return the total number of boats needed
        return numberOfBoats;
    }

Complexity:
Space complexity: O(1). Only variables are used. No extra array or any other data structure used.
Time Complexity: O(NlogN). This time is required to sort the array. After that, we find the number of boats in linear time.
Here N is the number of people who will travel.