Boats to Save People LeetCode 881

LeetCode 881 — Boats to Save People — gives you an array people where people[i] is the weight of the i-th person, and an integer limit representing the maximum weight a single boat can carry. At most 2 people can share a boat. Your goal is to return the minimum number of boats required to carry every person.

The constraint that each boat holds at most 2 people is critical. This means every boat carries either one person or two people, never more. The weight limit applies to the total weight of everyone in that boat. If two people board together, the sum of their weights must not exceed limit.

The minimum number of boats problem is a classic greedy exercise. The key insight is that to minimize boats, you want to maximize the number of boats that carry two people rather than one. Doing this optimally requires a careful pairing strategy.

The algorithm starts by sorting the people array in non-decreasing order. With the array sorted, we place one pointer at the left end (the lightest person) and one at the right end (the heaviest person). On each iteration we check whether the heaviest and lightest remaining people can share a boat.

If people[left] + people[right] <= limit, both can share a boat. Both board together, so we advance left forward and right backward. If the sum exceeds limit, the heaviest person must go alone since no one heavier than the lightest can possibly fit with them. We advance only right backward and count one boat.

We continue this process while left <= right. Each iteration consumes at least one person (right always decrements), guaranteeing termination. The boats counter increments by 1 on every iteration regardless of whether one or two people board.

The full algorithm is concise: sort people, then run a two-pointer loop. Left starts at index 0, right starts at n-1, and boats starts at 0. Each iteration of the while loop accounts for at least one boat.

When the two-pointer condition people[left] + people[right] <= limit is met, both pointers move inward. Otherwise only right moves inward. In both cases we increment boats. The loop terminates when left > right, meaning all people have been assigned to a boat.

The time complexity is O(n log n) dominated by the sort. The two-pointer pass is O(n) since left and right together traverse the array exactly once. Space complexity is O(1) beyond the sort, as no additional data structures are needed.

The greedy pairing strategy — heaviest with lightest — is provably optimal via an exchange argument. Suppose an optimal solution pairs the heaviest person H with some person M (not the lightest, L). We can swap M and L in the solution: H goes with L, and M either goes alone or with whoever L was previously paired with.

Because L is lighter than M, H + L <= H + M <= limit, so the swap is valid. The total number of boats does not increase — if H + M needed one boat, then H + L also fits in one boat and M may save a spot that reduces another boat. This exchange shows that pairing heavy with light never requires more boats.

An intuitive way to see it: the heaviest person is the hardest to pair. Giving them the best possible partner (the lightest person) maximizes the chance of a successful pairing. If even the lightest person cannot fit with the heaviest, then no pairing is possible for the heaviest and they must go alone — exactly what the algorithm does.

Consider people = [3, 2, 2, 1], limit = 3. After sorting the array becomes [1, 2, 2, 3]. We set left = 0, right = 3, boats = 0 and begin the two-pointer loop.

Iteration 1: people[left]=1, people[right]=3. Sum = 4 > 3, so 3 goes alone. right-- → right=2, boats=1. Iteration 2: people[left]=1, people[right]=2. Sum = 3 <= 3, so both board. left++ → left=1, right-- → right=1, boats=2.

Iteration 3: left=1 == right=1. people[left]=2 alone (only one person remains). right-- → right=0, boats=3. Now left > right, loop ends. Total boats = 3.

In Python: sort people, set left = 0 and right = len(people) - 1, boats = 0. Enter a while loop while left <= right. Inside the loop, check if people[left] + people[right] <= limit — if so, increment left. Always decrement right and increment boats. Return boats. Time O(n log n), space O(1).

In Java: Arrays.sort(people), then the same two-pointer pattern. Use int left = 0, right = people.length - 1, boats = 0. The while (left <= right) loop checks people[left] + people[right] <= limit to potentially advance left. Always advance right-- and boats++. Return boats.

A key implementation note: right always decrements on every iteration. This is because the heaviest person (at right) always boards a boat — either alone or with the lightest. We never skip the heaviest without placing them on a boat. left only increments when a valid pairing is found.

Boats to Save People belongs to the greedy pairing family — problems where optimal matching is achieved by sorting and using two pointers from opposite ends. Container With Most Water (LeetCode 11) uses the exact same two-pointer structure: start from both ends, always move the pointer pointing to the shorter line inward.

Gas Station (LeetCode 134) is another classic greedy where you identify the start point by tracking cumulative surplus. Hand of Straights (LeetCode 846) uses greedy grouping rather than pairing. In all these problems, the greedy strategy is justified by a similar exchange argument showing that local optimal choices lead to a global optimum.

Mastering the heavy-light pairing insight from LeetCode 881 builds intuition for a broad class of optimization problems. When you see "minimize the number of groups" with a capacity constraint and at-most-2 members, the sort-plus-two-pointer greedy is almost always the right approach.