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
- Sort the weights. The heaviest person must go on a boat, so pair them with the lightest remaining person whenever the combined weight fits.
- Use two pointers: if
people[l] + people[r] <= limit, both board and both pointers move; otherwise only the heaviest boards. - This greedy is optimal: leaving the lightest person for later can never help, because the heaviest person is the most constrained.
- Each iteration places at least one person, so the loop runs at most
ntimes.
💻 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 < ras the loop condition: a single remaining person still needs a boat, so the condition must bel <= r. - Forgetting that the heaviest person always boards: the
r -= 1must 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.