881. Boats to Save People

LeetCode 881, Boats to Save People, is a commonly asked interview problem at top tech companies like MAANG, specifically Amazon, Google, and Meta. It tests a candidate’s ability to justify greedy decisions and implement an efficient two-pointer solution under real-world constraints.

Problem statement

You are given an integer array people, where people[i] represents the weight of the ithi^{th}ith person, and an unlimited number of boats, where each boat can carry a maximum weight of limit. A single boat can take at most two people, as long as their combined weight does not exceed limit.

Your task is to compute the minimum number of boats required to carry everyone.

Constraints:

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

Examples

Naive approach: Trying all valid boat assignments

To find the minimum number of boats in a straightforward way, we can try every valid assignment of people to boats. Since each boat can carry at most two people and their combined weight must be ≤ limit, we pick a person and either send them alone or pair them with any other person who can fit with them.

After making that choice, we recurse on the remaining people and keep track of the smallest number of boats used across all possible choices. This works because it explores all possibilities, but it quickly becomes impractical because the number of ways to form pairings grows combinatorially as the input size increases.

An optimal solution using two pointers + greedy technique

Instead of exploring every possible pairing like the naive recursive approach, we can cut down the search by making a single, safe choice at each step. The key observation is that the heaviest person is the hardest to place, so we handle them first and try to pair them in the most efficient way. For a heavy person, the best partner to attempt is always the lightest remaining person, because that uses the least extra weight and gives the best chance of fitting within the limit. If lightest+heaviestlightest + heaviestlightest+heaviest is still too large, then the heaviest can’t pair with anyone at all, so they must go alone; otherwise, we pair them and continue with the rest.

To do the pairing reliably, we sort the weights. Sorting always keeps the lightest person at the start and the heaviest at the end. It then naturally gives us a two-pointer setup: one pointer for the lightest and the other for the heaviest.

This becomes a greedy technique because at each step we make the safest optimal choice: pair the heaviest with the lightest if possible (best chance to save a boat), otherwise send the heaviest alone (as they can’t pair with anyone). Each step is final, pointers move inward, and the boat count is minimized. In both cases, the pointers move inward until everyone is assigned, giving the minimum number of boats.

Step-by-step algorithm

1. Sort people in the ascending order.
2. Initialize two pointers: left = 0 for the lightest person, and right = n - 1 for the heaviest person. Set the number of boats used as boats = 0.
3. While left <= right:
   1. Use one boat, boats += 1, for the heaviest person at right.
   2. Try pairing the heaviest (people[right]) with the lightest person (people[left]). If people[left] + people[right] <= limit, pair them and increment left to move it inward.
   3. As the heaviest person is always taken, decrement right to move it inward.
4. Once the entire people array is traveresed, return boats.

1 / 6

Python code for the optimal solution

Now, let’s take a look at the Python code implementation of this solution:

def numRescueBoats(people, limit):
    # Sort weights so we can pair the lightest with the heaviest greedily.
    people.sort()

    left = 0                  # points to the lightest remaining person
    right = len(people) - 1   # points to the heaviest remaining person
    boats = 0

    # Keep assigning boats until everyone is placed.
    while left <= right:
        boats += 1  # We will use one boat for the heaviest person (at least).

        # Try to pair the lightest person with the heaviest person.
        # If they fit together, move both pointers inward (two people used).
        if people[left] + people[right] <= limit:
            left += 1

        # The heaviest person always boards this boat (alone or paired).
        right -= 1

    return boats


# Driver code
def main():
    test_cases = [
        ([1, 2], 3),
        ([3, 2, 2, 1], 3),
        ([3, 5, 3, 4], 5),
        ([2, 2, 2, 2], 4),
        ([1, 1, 3, 4], 4),
    ]

    for i, (people, limit) in enumerate(test_cases, 1):
        result = numRescueBoats(people, limit)
        print(f"{i}.\tpeople = {people}")
        print(f"\tlimit  = {limit}")
        print(f"\n\tOutput: {result}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

Sorting takes O(nlog⁡n), and the two-pointer scan takes O(n). So, the overall time complexity for the optimal solution is O(nlog⁡n).

Space complexity

We use Python’s sort function that is based on Tim Sort, which takes O(n) space for the sorting. Other than this, no extra space is used, so the overall space complexity is O(n).

Common mistakes to avoid and interview tips

This problem is greedy, but interviewers mainly want to see that your greedy choice is justified and your pointer movement is correct.

• Don’t try to optimize pairing beyond the two-pointer logic; it usually adds bugs.
• Always move the right pointer every loop, because the heaviest person is always placed.
• Use <= limit (not < limit) when checking if two people can share a boat.
• Be ready to explain: If the heaviest can’t pair with the lightest, they can’t pair with anyone. That’s the key correctness argument.