Log inSign up
mediumLeetCodeNot Started

Boats to Save People

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

You have an array people where people[i] is the weight of the i-th person, and each boat has a weight capacity limit. Each boat can carry at most two people at a time, provided their combined weight is <= limit.

Find the minimum number of boats required to rescue every person.

Example 1 · Example 1: Single and Paired:

Input: people = [1, 2], limit = 3
Output: 1
Explanation: 1 boat with (1, 2) since 1 + 2 = 3 <= 3.

Example 2 · Example 2: Multiple Boats:

Input: people = [3, 2, 2, 1], limit = 3
Output: 3
Explanation: Sorted: [1, 2, 2, 3].\nBoat 1: (3) alone (weight 3 <= 3).\nBoat 2: (1, 2) together (1 + 2 = 3 <= 3).\nBoat 3: (2) alone (weight 2 <= 3).\nTotal boats = 3.

Constraints:

  • 1 <= people.length <= 5 * 104
  • 1 <= people[i] <= limit <= 3 * 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why pairing extremes (min + max) is optimal when capacity is capped at 2 items.
  • Implement the two-pointer greedy pattern across C++, Java, Python, and JavaScript.
  • Analyze the difference between this and the general Bin Packing Problem (which is NP-Hard).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Capacity limit with fixed maximum items per container (at most 2 people).
  • Minimize total containers required.
  • Pairing optimization based on sum <= limit.

Algorithmic Decision Tree:

  • Sort weights ascending.
  • Set left = 0, right = n - 1.
  • If people[left] + people[right] <= limit -> left++ (light person shares boat).
  • Always right-- (heavy person gets on boat) and boats++.

Connected Patterns:

Assign CookiesTwo Sum II - Input Array Is SortedBag of Tokens

1. Brute Force — Quadratic Greedy Pairing with Used Array

Intuition

Sort people. Mark all people as unused. From right to left, find the next unplaced person. Then scan all unused lighter people to find the heaviest one who can share the boat. Mark them used and increment boat count.

When to apply: When N <= 200.

Algorithm

  1. Step 1: Sort people ascending.
  2. Step 2: Initialize boolean array used of size N to false.
  3. Step 3: For i from N - 1 down to 0: if used[i], continue.
  4. Step 4: Find largest j < i such that !used[j] and people[i] + people[j] <= limit.
  5. Step 5: If found, used[j] = true. Mark used[i] = true, increment boats.
  6. Step 6: Return boats.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int numRescueBoats(vector<int>& people, int limit) {
10 sort(people.begin(), people.end());
11 int n = people.size();
12 vector<bool> used(n, false);
13 int boats = 0;
14
15 for (int i = n - 1; i >= 0; --i) {
16 if (used[i]) continue;
17 used[i] = true;
18 for (int j = i - 1; j >= 0; --j) {
19 if (!used[j] && people[i] + people[j] <= limit) {
20 used[j] = true;
21 break;
22 }
23 }
24 boats++;
25 }
26 return boats;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> people = {3, 2, 2, 1};
33 int limit = 3;
34 cout << "Min boats: " << sol.numRescueBoats(people, limit) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N^2) — Outer loop runs N times, inner loop scans up to N times.
  • Space complexity: O(N) — Boolean used array of size N.

Why Brute Force Doesn't Scale:

With N = 50,000, N2 is 2.5 * 109 operations, which times out. Two pointers on sorted array runs in ~15ms.

For N = 50,000: O(N log N) requires ~8 * 105 operations, executing in under 20ms.

2. Better — Frequency Bucket Array (Counting Sort Style)

Intuition

Since weights are integers <= limit, we can build a frequency map or count array. Then use two pointers over the distinct weights: match highest weight with lowest weight, decrementing frequencies.

When to apply: When limit is small (limit <= 30,000).

Algorithm

  1. Step 1: Create count array of size limit + 1 and tally person weights.
  2. Step 2: left = 1, right = limit.
  3. Step 3: While left <= right: find next non-zero left and right.
  4. Step 4: If left + right <= limit, pair them (decrement both counts); else right goes alone.
  5. Step 5: Return boats count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int numRescueBoats(vector<int>& people, int limit) {
9 vector<int> count(limit + 1, 0);
10 for (int p : people) count[p]++;
11
12 int left = 1, right = limit;
13 int boats = 0;
14
15 while (left <= right) {
16 while (left <= right && count[left] == 0) left++;
17 while (left <= right && count[right] == 0) right--;
18 if (left > right) break;
19
20 if (left + right <= limit) {
21 if (left == right) {
22 boats += (count[left] + 1) / 2;
23 break;
24 }
25 int pairs = min(count[left], count[right]);
26 boats += pairs;
27 count[left] -= pairs;
28 count[right] -= pairs;
29 } else {
30 boats += count[right];
31 count[right] = 0;
32 }
33 }
34 return boats;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> people = {3, 2, 2, 1};
41 cout << "Min boats: " << sol.numRescueBoats(people, 3) << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N + limit) — Counting takes O(N). Two pointers traverse limit buckets in O(limit).
  • Space complexity: O(limit) — Bucket array of size limit + 1.

3. Optimal — Two Pointers on Sorted Array

Intuition

Sort people ascending. Left points to lightest (0), right to heaviest (n - 1). If people[left] + people[right] <= limit, lightest person shares the boat, so left++. In all cases, heaviest person takes the boat, so right--. Increment boats in every iteration until left > right.

When to apply: Always for Boats to Save People.

Algorithm

  1. Step 1: Sort people array in ascending order.
  2. Step 2: Initialize left = 0, right = people.length - 1, boats = 0.
  3. Step 3: While left <= right: if people[left] + people[right] <= limit, left++.
  4. Step 4: Decrement right-- and increment boats++.
  5. Step 5: Return boats.

Interactive Trace for Boats to Save People

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compare lightest people[0]=1 with heaviest people[3]=3
Visual state
Values and pointers at this exact step
pointers
S
waiting
waiting
waiting
boat_1
0
↑ left
1
2
3
↑ right
Check / comparison
1 + 3 = 4 > 3 (Limit exceeded)
Decision / next transition
Person 3 must go alone. boats = 1, right = 2.
Why this step matters

Step 1: Compare lightest people[0]=1 with heaviest people[3]=3. 1 + 3 = 4 > 3. Cannot share!

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int numRescueBoats(vector<int>& people, int limit) {
10 sort(people.begin(), people.end());
11 int left = 0;
12 int right = people.size() - 1;
13 int boats = 0;
14
15 while (left <= right) {
16 if (people[left] + people[right] <= limit) {
17 left++;
18 }
19 right--;
20 boats++;
21 }
22 return boats;
23 }
24};
25
26int main() {
27 Solution sol;
28 vector<int> people = {3, 2, 2, 1};
29 int limit = 3;
30 cout << "Min boats: " << sol.numRescueBoats(people, limit) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N). Two-pointer scan takes O(N).
  • Space complexity: O(1) auxiliary — In-place two-pointer traversal uses O(1) extra space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Quadratic Greedy Scan with Visited ArrayO(N^2)O(N)Sort people. For each heaviest unplaced person, scan all lighter unplaced people to find the heaviest one who can share a boat.Linear scan per person.
2.Better — Frequency / Bucket Array CountingO(N + limit)O(limit)Count frequencies of each weight in a bucket array of size limit + 1. Use two pointers over the bucket indices.Memory and bucket iteration.
3.Optimal — Two Pointers on Sorted ArrayOptimalO(N log N)O(1) auxiliarySort people ascending. Left at 0, right at N - 1. If people[left] + people[right] <= limit, left++. Always right-- and increment boats.Sorting step.

Common Pitfalls & Crucial Edge Cases

Assuming more than 2 people can board

The problem specifies at most TWO people per boat.

Incrementing left when sum > limit

The light person did NOT board; only the heavy person boards.

Using strictly less than (<) instead of less-than-or-equal (<=)

Combined weight exactly equal to limit is valid.

Crucial Edge Cases to Validate:

  • N = 1 — Exactly 1 boat required; returns 1.
  • Every person weighs limit — Each person must take their own boat; returns N.
  • Every pair fits within limit — Exactly ceil(N / 2) boats required.
  • Identical weights — Handled seamlessly by two-pointer convergence.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Note the crucial constraint: 'at most 2 people per boat'. This makes the problem solvable in O(N log N) with greedy two-pointers. If boats could hold arbitrary numbers of people, it would be the NP-Hard Bin Packing Problem!
  2. State the two-pointer invariant clearly to the interviewer.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the heaviest person always board a boat in every step?

Back to DSA Sheet