MediumCoding

Boats to Save People

Asked at

IDFC FIRST Bank

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Sort people by weight and place pointers at the lightest and heaviest.
02The heaviest remaining person must take the next boat.
03Pair that person with the lightest only if they fit, then count one boat.
04Send the heaviest alone when even the lightest remaining person cannot fit.

Reference answer

Sort the weights. Let left be the lightest remaining person and right the heaviest. The heaviest person must leave in the next boat because pairing two lighter people does not remove that unavoidable need. If people[left] + people[right] <= limit, pair them and advance both pointers. Otherwise the heaviest cannot pair with even the lightest remaining person, so send the heaviest alone and decrement only right. Count one boat per iteration. This greedy choice never harms a future pairing: when a pair is possible, using the lightest companion preserves heavier people for other boats; when it is impossible, no companion can fit. Sorting takes O(n log n), the scan is O(n), and extra space depends on sorting. The problem's at-most-two-people rule is essential; larger boat capacities lead to a different packing problem.

Then expect these follow-ups

Why must the heaviest remaining person be handled now?
Tests: greedy proof
What changes if a boat can carry three people?
Tests: problem complexity

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question