Fewest Rafts

MediumTwo Pointers

Problem

A river-tour company must ferry hikers across. Hiker i weighs weights[i]. Every raft carries at most two hikers whose combined weight is at most limit; every single hiker fits on a raft alone.

Return the minimum number of rafts needed to carry everyone.

Example 1

Input:
weights = [70, 50, 80, 50], limit = 100
Output:
3

Rafts: (50, 50), (70), (80).

Example 2

Input:
weights = [30, 40, 50], limit = 100
Output:
2

(50, 40) and (30) — or (30, 50) and (40); three hikers cannot share one raft.

Constraints

  • 1 ≤ weights.length ≤ 5·10^4
  • 1 ≤ weights[i] ≤ limit ≤ 3·10^4

Hint

Show the first hint

The heaviest hiker needs a raft no matter what. Who is the best partner for them?

Walkthrough

How to approach it

01Clarify before coding

  • At most two per raft regardless of weight? Yes, even if three light hikers would fit by weight.
  • Can a single hiker exceed limit? No, everyone fits alone.
  • Do we return the rafts or only their count? Only the count.

02Brute force

Try all ways of pairing hikers (a maximum matching on the 'fits together' graph) and minimise rafts.

Cost: Exponential with naive search, or O(n³) with general matching; overkill for this structure.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.