Boats to Save People

How it works

When the range of weights is limited, counting sort can be faster than comparison-based sorting. We count the frequency of each weight, then reconstruct the sorted array. After sorting, we apply the same two-pointer greedy strategy as before.

Steps

1. Find the maximum weight in the array.
2. Create a count array of size (max + 1) and count the frequency of each weight.
3. Reconstruct the sorted array by iterating through the count array.
4. Apply the two-pointer approach:
   • Initialize left at 0 and right at the end.
   • While left is less than or equal to right:
     • The heaviest person takes a boat.
     • If the lightest person fits with them, include them too.
5. Return the boat count.

Complexity

• Time complexity: O(n)
• Space complexity: O(m)

Where n is the size of the input array and m is the maximum value in the array.

Things to watch for

Forgetting to Sort the Array First

The two-pointer approach only works on sorted arrays. Attempting to pair people without sorting will not produce the minimum number of boats because you cannot guarantee pairing the heaviest with the lightest.

Trying to Fit More Than Two People per Boat

The problem states each boat can carry at most 2 people, regardless of weight. A common mistake is trying to fit three or more light people in one boat.

Not Moving the Right Pointer First

The heaviest person always needs a boat. A mistake is checking if the lightest person fits first, which can lead to incorrect pointer movement when the lightest person alone exceeds the remaining capacity.

from typing import List

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        m = max(people)
        count = [0] * (m + 1)
        for p in people:
            count[p] += 1

        idx, i = 0, 1
        while idx < len(people):
            while count[i] == 0:
                i += 1
            people[idx] = i
            count[i] -= 1
            idx += 1

        res, l, r = 0, 0, len(people) - 1
        while l <= r:
            remain = limit - people[r]
            r -= 1
            res += 1
            if l <= r and remain >= people[l]:
                l += 1
        return res

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int m = *max_element(people.begin(), people.end());
        vector<int> count(m + 1, 0);
        for (int p : people) {
            count[p]++;
        }

        int idx = 0, i = 1;
        while (idx < people.size()) {
            while (count[i] == 0) {
                i++;
            }
            people[idx++] = i;
            count[i]--;
        }

        int res = 0, l = 0, r = people.size() - 1;
        while (l <= r) {
            int remain = limit - people[r--];
            res++;
            if (l <= r && remain >= people[l]) {
                l++;
            }
        }
        return res;
    }
};