algoadvance

Leetcode 881. Boats to Save People

Problem Statement

You are given an array people where people[i] is the weight of the i-th person, and an integer limit which represents the maximum weight a boat can carry. Each boat can carry no more than two people at the same time, provided the sum of weights of those people is at most limit.

Your task is to find the minimum number of boats required to carry every given person.

Clarifying Questions

1. Q: Can a person be on more than one boat? A: No, each person must be on exactly one boat.

2. Q: Can there be a scenario where it is impossible to fit a person within the given weight limit? A: No, you can assume that it is always possible to save everyone.

3. Q: Can the input array be empty? A: Since the problem asks to find the minimum number of boats to save people, we can assume the input array people will have at least one element.

4. Q: How should we handle edge cases, like when all people have the same weight? A: The solution should account for all edge cases. Sorting the array will help manage such scenarios.

Strategy

1. Sort the List: Start by sorting the list of people based on their weights.
2. Two Pointers: Use a two-pointer approach. One pointer (i) starts from the beginning (lightest person) and another pointer (j) starts from the end (heaviest person).
3. Pair and Count: Try to pair the lightest person with the heaviest person who can fit in the same boat. If they can be paired, move both pointers inward; otherwise, move only the pointer for the heaviest person inward.
4. Move Inward: Continue this process until all people are assigned to boats.

Code

import java.util.Arrays;

public class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0;
        int j = people.length - 1;
        int boats = 0;
        
        while (i <= j) {
            // If the lightest and the heaviest person can be in the same boat
            if (people[i] + people[j] <= limit) {
                i++;
                j--;
            } else {
                // Only the heaviest person takes a boat
                j--;
            }
            boats++;
        }
        
        return boats;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] people1 = {1, 2};
        int limit1 = 3;
        System.out.println(solution.numRescueBoats(people1, limit1)); // Output: 1

        int[] people2 = {3, 2, 2, 1};
        int limit2 = 3;
        System.out.println(solution.numRescueBoats(people2, limit2)); // Output: 3

        int[] people3 = {3, 5, 3, 4};
        int limit3 = 5;
        System.out.println(solution.numRescueBoats(people3, limit3)); // Output: 4
    }
}

Time Complexity

• Sorting: O(n log n), where n is the number of people.
• Two-pointers traversal: O(n), as each person is considered at most once.

Therefore, the overall time complexity is O(n log n) due to the sorting step.

Space Complexity

• The space complexity is O(1) for the sorting and two-pointer operations, excluding the input space.

This solution is efficient and handles the problem requirements within optimal time and space constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?