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 that a boat can carry. Each boat can carry at most two people at the same time, provided the sum of their weights is within the limit. Return the minimum number of boats required to carry every person.

Strategy

To solve this problem efficiently, we can use a two-pointer technique after sorting the array of people’s weights:

  1. Sort the Array: Start by sorting the people array.
  2. Two Pointers Technique: Use two pointers (left and right) to represent the lightest and heaviest person, respectively.
  3. Pairing Individuals:
    • If the sum of the weights of the people pointed by the two pointers is within the limit, move both pointers inward (i.e., left++ and right--).
    • Otherwise, move only the right pointer inward (i.e., right--), indicating that the heaviest person must go alone in a boat.
  4. Counting Boats: Each iteration of pairing or moving a single person will increment the count of boats required.

Clarifying Questions

  1. Input Constraints: Are weights guaranteed to be positive integers?
  2. Array Size: Is there any constraint on the size of the people array?
  3. Edge Cases: Are there any special cases we need to handle explicitly, such as empty arrays or all weights being the same?

Code

Here is the C++ implementation:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int left = 0, right = people.size() - 1;
        int boats = 0;
        
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                // They can share a boat
                left++;
                right--;
            } else {
                // The heaviest person goes alone
                right--;
            }
            boats++;
        }
        
        return boats;
    }
};

Time Complexity

Thus, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

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

Feel free to ask if you need further clarifications or if there are specific edge cases you’d like to discuss!

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