⚡Flashcard Drill➔
NeetCode #207LC-881MediumTwo PointersNC 250
← Back to All Problems

#207 · #881 · Boats to Save People(救生艇)

📌 Problem Statement & Constraints

You are given an array people where people[i] is the weight of the i-th person, and a limit on the total weight each boat can carry. Each boat carries at most two people. Return the minimum number of boats. Constraints: 1 <= people.length <= 5 * 10^4, 1 <= people[i] <= limit <= 3 * 10^4.

💡 Core Algorithmic Approaches

  1. Sort the weights. The heaviest person must go on a boat, so pair them with the lightest remaining person whenever the combined weight fits.
  2. Use two pointers: if people[l] + people[r] <= limit, both board and both pointers move; otherwise only the heaviest boards.
  3. This greedy is optimal: leaving the lightest person for later can never help, because the heaviest person is the most constrained.
  4. Each iteration places at least one person, so the loop runs at most n times.

💻 Benchmark Python3 Implementation

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        l, r = 0, len(people) - 1
        boats = 0
        while l <= r:
            if people[l] + people[r] <= limit:
                l += 1                 # the lightest person also boards
            r -= 1                     # the heaviest always boards
            boats += 1
        return boats

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates; the two-pointer scan is O(n).
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Not sorting: the greedy pairing requires the weights to be ordered.
  • Using l < r as the loop condition: a single remaining person still needs a boat, so the condition must be l <= r.
  • Forgetting that the heaviest person always boards: the r -= 1 must happen on every iteration, regardless of the branch.
  • Trying to pair the two lightest or the two heaviest: the optimal pairing is always lightest-with-heaviest.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems