Boats to Save People

Difficulty: Medium Source: NeetCode

Problem

You are given an array people where people[i] is the weight of the i-th person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Example 1: Input: people = [1,2], limit = 3 Output: 1

Example 2: Input: people = [3,2,2,1], limit = 3 Output: 3

Example 3: Input: people = [3,5,3,4], limit = 5 Output: 4

Constraints:

• 1 <= people.length <= 5 * 10^4
• 1 <= people[i] <= limit <= 3 * 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy Algorithms — pairing the lightest and heaviest to minimize wasted capacity
• Sorting — enabling two-pointer pairing
• Two Pointers — simultaneously processing from both ends of a sorted array

1. Brute Force

Intuition

Sort the people by weight. For each heaviest remaining person, try to find the heaviest other person they can share a boat with (greedy pairing). This avoids the two-pointer elegance but still achieves a correct result. It’s O(n²) because each pairing scan iterates through the remaining people.

Algorithm

1. Sort people.
2. Use a used set to track who has boarded.
3. For each person (heaviest first, iterating from the right):
   • If already used, skip.
   • Try to find the heaviest unused person on the left side who fits.
   • Either way, assign a boat and mark both as used.
4. Return the boat count.

Solution

def numRescueBoats(people, limit):
    people.sort()
    n = len(people)
    used = [False] * n
    boats = 0

    for i in range(n - 1, -1, -1):
        if used[i]:
            continue
        boats += 1
        used[i] = True
        # Try to pair with the lightest unused person
        for j in range(n):
            if not used[j] and people[i] + people[j] <= limit:
                used[j] = True
                break

    return boats


print(numRescueBoats([1, 2], 3))        # 1
print(numRescueBoats([3, 2, 2, 1], 3))  # 3
print(numRescueBoats([3, 5, 3, 4], 5))  # 4

Complexity

• Time: O(n²)
• Space: O(n)

2. Sort + Two Pointers

Intuition

Sort the array. Now greedily try to pair the lightest person (left pointer) with the heaviest person (right pointer). If they fit together on one boat, great — both board and we move both pointers inward. If they don’t fit, the heaviest person takes a boat alone (no one lighter can fit with them since we already tried the lightest option). Either way, the right pointer moves left. Count one boat per iteration.

Algorithm

1. Sort people.
2. Initialize left = 0, right = len(people) - 1, boats = 0.
3. While left <= right:
   • If people[left] + people[right] <= limit: increment left (both board together).
   • Decrement right (heaviest person always boards).
   • Increment boats.
4. Return boats.

Solution

def numRescueBoats(people, limit):
    people.sort()
    left, right = 0, len(people) - 1
    boats = 0

    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1   # Lightest person shares the boat
        right -= 1      # Heaviest person always takes a boat
        boats += 1

    return boats


print(numRescueBoats([1, 2], 3))        # 1
print(numRescueBoats([3, 2, 2, 1], 3))  # 3
print(numRescueBoats([3, 5, 3, 4], 5))  # 4
print(numRescueBoats([2, 2], 6))        # 1

Complexity

• Time: O(n log n) — dominated by sorting
• Space: O(1)

Common Pitfalls

Using left < right instead of left <= right. When only one person remains (left == right), they still need a boat. The <= ensures the last person is counted.

Moving right only when a pair is found. The heaviest person always takes a boat regardless of whether they share it — the right pointer decrements unconditionally. Only left advances conditionally.

Trying to pair the heaviest person with the second-heaviest. The greedy insight is to pair the heaviest with the lightest. Pairing two heavy people often wastes capacity and increases the total boat count.