Two Pointers — Boats to Save People
↗ LeetCode: Boats to Save People · Medium · pattern chapter →
Each boat carries ≤ 2 people totaling ≤ limit. Minimize boats.
Example 1 — people=[1,2], limit=3 → 1Example 2 — people=[3,2,2,1], limit=3 → 3Example 3 — people=[3,5,3,4], limit=5 → 4
Constraints — 1 ≤ n ≤ 5·10⁴. Brute enumeration of all pairings is (n/2)! ≈ 10²⁰⁰⁰⁰ — impossible. Sort + two-pointer greedy is O(n log n). Brute pairs each person with every other — O(n²) = 2.5·10⁹ ops at n=5·10⁴ (TLE). Sort + two-pointer greedy is O(n log n) = ~10⁶ ops.
Interview timer00:00
Approach 1 — Brute enumerate pairings (reference)
Intuition. For each way to partition people into groups of 1 or 2 (each ≤ limit), count boats. Return the minimum.
Complexity — Time O((n/2)!) partitions. At n=10 that's 3,628,800 — feasible but stops there. Just state this for completeness. In an interview say "there's a greedy exchange argument that gives O(n log n)."
Approach 2 — Sort + greedy two-pointer (canonical)
Insight. Sort. Pair the heaviest with the lightest if they fit; otherwise the heaviest goes alone.
Why optimal — exchange argument. If the heaviest person can't share with the lightest available, they can't share with anyone (everyone else is at least as heavy as the lightest). So the heaviest is forced into a boat alone or with the lightest — no other choice can help.
int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int l = 0, r = people.length - 1, boats = 0;
while (l <= r) {
if (people[l] + people[r] <= limit) l++;
r--; boats++;
}
return boats;
}Complexity — Time O(n log n); Space O(1). Say aloud in an interview: "same 'heaviest + lightest' exchange argument as fair-pairing problems in Balanced Load Assignment and Sum-of-Pairs Minimization."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute pairings | O((n/2)!) | O(n) | Reference; dies past n=12 |
| Sort + greedy 2p | O(n log n) | O(1) | Canonical |
When to use which
- "Pair heaviest + lightest greedy" → applies to boats, task scheduling, item packing.
- "3+ per boat" → generalizes with DP or different greedy.