AlgoMaster Logo

Boats to Save People

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have a group of people, each with a known weight, and we need to ferry everyone using the fewest boats possible. Each boat has a weight limit and holds at most two people. The "at most two" rule shapes everything: even if three lightweight people would fit under the weight limit, a boat can only take two.

The question becomes: how do we pair people so that as many boats as possible carry two riders? The fewer solo riders, the fewer total boats.

Pairing works best when we match the heaviest person who still needs a boat with the lightest person available. If even the lightest person cannot share a boat with the heaviest, no one can, and the heaviest rides alone. Both approaches below apply this rule; they differ in how fast they find the heaviest and lightest remaining people.

Key Constraints:

  • 1 <= people.length <= 5 * 10^4 → With n up to 50,000, O(n log n) sorting plus a linear pass fits comfortably. An O(n^2) approach that rescans the array for every boat is around 2.5 billion operations in the worst case, which is too slow.
  • 1 <= people[i] <= limit <= 3 * 10^4 → Every person's weight is at most the limit, so everyone fits in a boat alone if necessary. There is no "impossible" person.

Approach 1: Brute Force (Repeated Scans)

Intuition

The heaviest person needs a boat no matter what, so assign them one. Their best possible partner is the lightest remaining person: if even that pairing exceeds the limit, no pairing involving the heaviest person works, and they ride alone. Repeat until everyone has a boat.

The choice of partner matters. Pairing each person with the first partner that fits can waste capacity. For people = [1, 1, 4, 4] and limit = 5, pairing the two 1s together leaves the two 4s to ride alone, for 3 boats, while pairing each 1 with a 4 uses 2 boats. Always taking the heaviest and lightest remaining people avoids this.

Without sorting, finding the heaviest and lightest remaining people requires scanning the whole array on every pass, which makes this O(n^2).

Algorithm

  1. Create a boolean array used of size n and a counter remaining = n.
  2. Initialize boats = 0.
  3. While remaining > 0:
    • Scan the array for the heaviest unassigned person. Assign them a boat: mark them used, decrement remaining, increment boats.
    • Scan again for the lightest unassigned person. If one exists and the two weights sum to at most limit, put them on the same boat: mark them used and decrement remaining.
  4. Return boats.

Visualization and Code

Loading animation...

The algorithm produces the correct answer but spends almost all its time rescanning the array. Sorting puts the lightest person at one end and the heaviest at the other, so two pointers moving inward can replace the repeated scans.

Approach 2: Greedy with Two Pointers (Optimal)

Intuition

Sort the people by weight. The lightest person is now at the front, the heaviest at the back, so the two people the greedy rule cares about sit at the two ends of the array. Two pointers track them: light starting at index 0 and heavy starting at the last index.

For each boat, put the heaviest remaining person on it (they need a boat regardless). Then check whether the lightest remaining person can join: if people[light] + people[heavy] <= limit, they share the boat and both pointers move inward. Otherwise the heavy person rides alone and only the heavy pointer moves.

Algorithm

  1. Sort the people array in ascending order.
  2. Initialize two pointers: light = 0 and heavy = people.length - 1.
  3. Initialize boats = 0.
  4. While light <= heavy:
    • If people[light] + people[heavy] <= limit, the lightest and heaviest can share a boat. Move light forward.
    • Regardless, the heaviest person gets on this boat. Move heavy backward.
    • Increment boats.
  5. Return boats.

Visualization and Code

Loading animation...