← DSA Atlas
Dedicated problem page · #881

Boats to Save People

MediumTwo PointersGreedy pairing of extremesTwo pointers on a sorted array
Solve on LeetCode ↗
881
MediumTwo PointersTwo pointers on a sorted arrayGreedy pairing of extremes

Boats to Save People

Given an array people where people[i] is the weight of the i-th person and an integer limit, each boat carries at most two people whose combined weight is at most limit. Return the minimum number of boats needed to carry everyone.

Open official problem prompt ↗
In plain English

Ferry everyone across using as few two-seat, weight-limited boats as possible.

Picture it like this

Loading an elevator with a strict weight limit and a two-person cap: you send the heaviest rider, and squeeze in the lightest person waiting if they both fit — otherwise the heavy rider goes solo.

Example
Input
people = [3, 2, 2, 1], limit = 3
Output
3
Why
Boats: (1,2), (2) alone, (3) alone — three boats, and no arrangement uses fewer.
Constraints
1 <= people.length <= 5 * 10^41 <= people[i] <= limit <= 3 * 10^4
Pattern lesson

See the pattern, then code

Greedy pairing of extremes
Recognition clue

At most two per boat with a sum cap, minimizing count, is the classic 'pair the lightest with the heaviest' greedy — sort then close in from both ends.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. The heaviest person must sail regardless. Give them the lightest remaining companion: if even that pair exceeds the limit, no one can share with them, so they go alone. Every boat is filled as fully as possible, which minimizes the total.

New words, made simpleKnow these before the algorithm
Greedy choice
Making the locally optimal pairing (lightest with heaviest) at each step.
Two-pointer sweep
Indices closing in from the sorted array's ends.
Capacity
The per-boat weight limit shared by at most two people.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Sort and pair-match by search

Works but the search is unnecessary — the lightest is always the best partner.

For the heaviest, search for the best partner that fits.

Time O(n log n)Space O(1)
Best choiceSort + two pointers, greedy

Optimal and simplest; dominated by the sort.

Pair the current lightest with the current heaviest when they fit; the heaviest always boards.

Time O(n log n)Space O(1)
The rule we keep true

Invariant

At every step the heaviest unseated person boards a boat, and that boat also carries the lightest remaining person exactly when they fit — so no boat ever leaves with wasted room that a lighter person could have used.

Why this is correct

Reasoning

The heaviest person needs a boat no matter what. If the lightest person cannot share with them, then no one can (everyone else is at least as heavy), so a solo trip is forced and optimal. If the lightest can share, pairing them wastes nothing: the lightest is the easiest to place elsewhere, so using them here never blocks a better future pairing. An exchange argument shows any optimal solution can be rearranged into this greedy one without increasing boat count.

The algorithm in three movesSay these aloud before coding
1Sort people ascending

sorted [1,2,2,3]; i=0,j=3: 1+3=4>3 -> 3 alone, boats=1

2Set i at the lightest and j at the heaviest

i=0,j=2: 1+2=3<=3 -> pair, boats=2

3If people[i] + people[j] <= limit, board both (i += 1)

i=1,j=1: single 2, boats=3

4Always board the heaviest (j -= 1) and count one boat

5Repeat until i > j

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
22
33
1 · Readpeople[0]=1, people[3]=3
2 · AskDo the lightest and heaviest fit together?
3 · Update statei=0, j=3, boats=0
4 · Result1+3=4 > 3 -> 3 sails alone; j=2, boats=1.
Key takeaway

After sorting, the lightest (1) is offered to the heaviest (3); 4>3 so the 3 sails alone.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Sort ascending

    Ordering by weight lets the two pointers represent lightest and heaviest.

  2. 2
    Lines 4-5Initialize pointers and counter

    i at the lightest, j at the heaviest, boats at zero.

  3. 3
    Lines 6-11Greedy loop

    Advance i only when the pair fits, always retreat j, and count a boat each iteration since the heaviest always sails.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single person — one boat
  • Every person alone because even the two lightest exceed the limit (though constraints guarantee each individual fits)
  • All pairs fit — exactly ceil(n/2) boats
  • Two people whose weights sum to exactly limit — they share one boat
!

Common beginner mistakes

  • Forgetting to increment the boat count when a person sails alone
  • Advancing the heavy pointer j only when a pair forms — j must always move since the heaviest always boards
  • Skipping the i <= j (inclusive) check and missing the final middle person
Check your understanding

Why is pairing the lightest with the heaviest never worse than any other pairing for the heaviest person?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima