Domain 2MediumMEDIUM

Boats to Save People

Uses a greedy strategy with sorting and two pointers to pair the heaviest person with the lightest compatible partner, minimizing boat count.

Domain: medium•Updated: 2026-09-03
#Greedy#Sorting/Two Pointers#$O(N log N)$#$O(1)

Problem Breakdown

We are tasked with finding the minimum number of boats required to transport all people given a weight limit per boat (limit) and a constraint that each boat can carry at most two people.

Inputs:

  • people: A list of integers representing individual weights.
  • limit: An integer representing the maximum total weight capacity for one boat.

Outputs:

  • An integer representing the minimum number of boats needed.

Constraints & Edge Cases to Consider:

  1. Capacity Constraint: Each person’s weight is guaranteed to be less than or equal to the limit (people[i] <= limit). This means every single person can fit in a boat alone, so we don’t need to handle impossible cases where someone cannot board at all.
  2. Boat Capacity Limit: A boat takes either one or two people. We must maximize this capacity (two people) whenever possible to minimize the total count of boats used.
  3. Sorting Requirement: To efficiently check if a light person can pair with a heavy person, we need ordered access to weights. Sorting is essential here.
  4. Empty Input: While constraints specify people.length >= 1, robust code should handle an empty list gracefully (returning 0).

Intuition

A brute-force approach would try every possible combination of two people for each boat, which leads to exponential complexity or at least O(N2)O(N^2) if we iterate through pairs naively. This is inefficient given the input size (5×1045 \times 10^4).

The key insight here is Greedy Strategy. To minimize boats, we want to maximize how many people fit into each boat (ideally two).

  • The heaviest person needs a boat regardless of who they are paired with.
  • If the lightest available person can pair with the heaviest without exceeding limit, it’s always optimal to do so. Why? Because if we don’t use the lightest person now, that “light” capacity is wasted on someone heavier later (who might not fit anyway), or saved for a lighter boat which isn’t possible since everyone else is ≥\ge current lightest weight.
  • If even the lightest available person cannot pair with the heaviest (people[left] + people[right] > limit), then no one can pair with that heaviest person (since all others are heavier than or equal to left). The heaviest must go alone.

Approach

  1. Sort the people array in ascending order. This allows us to access the lightest and heaviest remaining people using pointers efficiently.
  2. Initialize two pointers:
    • left: Points to the start of the sorted list (lightest person).
    • right: Points to the end of the sorted list (heaviest person).
  3. Iterate while left <= right. This loop represents processing one boat at a time.
  4. Inside the loop:
    • Check if people[left] + people[right] <= limit.
    • If True: The lightest and heaviest can share a boat. Move both pointers (left++, right--). This counts as using one boat for two people.
    • If False: They cannot fit together. Since the array is sorted, no other person (who weighs more than or equal to people[left]) will be able to pair with people[right]. The heaviest must go alone. Move only the right pointer (right--). This counts as using one boat for one person.
  5. Increment a counter variable boats in every iteration, representing that we have dispatched one boat (either carrying two or one).
  6. Return the final count of boats.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N). The dominant operation is sorting the array (NN people), where NN is people.length. The subsequent linear scan with pointers takes O(N)O(N), so it does not change the overall complexity class.
  • Space Complexity: O(1)O(1) auxiliary space (excluding input storage). We only use two integer variables for pointers and a counter. Python’s sort implementation uses stack space proportional to log⁡N\log N in worst case recursion depth or buffer depending on version, but logically we treat it as constant extra memory usage relative to the logic flow.

Solution

def numRescueBoats(people: list[int], limit: int) -> int:
    # Sort people by weight to use two-pointer technique efficiently
    people.sort()
    
    left = 0           # Pointer for lightest person available
    right = len(people) - 1  # Pointer for heaviest person available
    boats = 0          # Counter for total boats needed
    
    while left <= right:
        # If the lightest and heaviest can fit together, pair them up.
        if people[left] + people[right] <= limit:
            left += 1
        
        # The heaviest person always boards this boat (either alone or with someone).
        # We move the right pointer regardless of whether they paired up.
        boats += 1
        right -= 1
    
    return boats

# Example usage matching problem description
print(numRescueBoats([3,2,2,1], 3))   # Output: 3

Edge Cases Handled

  • Single Person: The loop runs once (left == right), increments boats, and terminates correctly.
  • All Fit in Pairs: If every lightest person pairs with the heaviest until one remains, pointers converge efficiently without unnecessary iterations.
  • Heavier than Limit (Impossible): Constraints guarantee people[i] <= limit. Even if this weren’t true, logic would fail gracefully or require a check before pairing; here it is guaranteed safe.
  • Limit Matches Heaviest Weight: If the heaviest person weighs exactly limit, they cannot pair with anyone else since weights are ≥1\ge 1. The condition fails (left + right > limit), so they go alone, which is correct behavior.