Medium · Lightest-Heaviest Pairing
Understand → Visualise → Practice.
Each boat holds at most two people within a weight limit. Return the minimum boats.
Sort the weights. The heaviest person must board some boat; the best partner is the lightest remaining person. If even they don't fit together, the heaviest goes alone.
Order weights ascending; pointers at the lightest and heaviest.
If lightest + heaviest ≤ limit, the lightest boards too (move the left pointer).
Always move the right pointer and add one boat until the pointers cross.
O(n log n) time and O(1) extra space.
Pairing the two lightest first can leave two heavy people who each need a boat.
Read the full guide first: Two Pointers and Sliding Windows.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.