Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Two pointers

Fewest boats under a weight limit

Medium · Target 15 minutes · Two pointers

people[i] is the weight of person i. Each boat carries at most two people, and their total weight may not exceed limit. Nobody weighs more than limit. Return the smallest number of boats that carries everyone.

Examples

InputOutputWhy
people = [3, 2, 2, 1], limit = 33Boats (1, 2), (2) and (3).
people = [3, 5, 3, 4], limit = 54No two people fit together.

Constraints

  • 1 ≤ n ≤ 5 × 10⁴
  • 1 ≤ people[i] ≤ limit ≤ 3 × 10⁴

Hints

Hint 1

Every boat holds one or two people, so minimising boats means maximising the number of pairs. Which person is hardest to pair?

Hint 2

The heaviest person. Who is the best partner for them, if anyone is?

Hint 3

Sort. Look at the lightest and the heaviest left. If they fit together, pair them; if not, the heaviest cannot pair with anyone and goes alone.

Where people lose marks

  • Pairing the heaviest with the heaviest person who still fits. It also gives the optimum, but needs a search per step and a longer proof.
  • Stopping at i < j and forgetting the last person when i = j: they need a boat too.
Console⌘/Ctrl + Enter runs

Write a solution and run it against the real test table.


Keep going

Preparing for a real process? Quant interview preparation, or book a free 20-minute call.