How do you solve Boats to Save People?

Sort the people array. Initialize two pointers: left at start, right at end. While left <= right, if people[left] + people[right] <= limit, increment left to pair with right. Always decrement right and increment boat count. Return the total boat count after processing all people.

What pattern does Boats to Save People use?

The Pattern: Two Pointers (Greedy Pairing) The Heuristic: Always attempt to pair the heaviest person with the lightest person who can fit with them; if not possible, send the heaviest alone. This greedy contraction reduces the problem size optimally in linear time.

Boats to Save People | Two Pointers

Q: What is the time complexity of Boats to Save People?

O(n log n). Sorting the array takes O(n log n), and the two-pointer traversal is O(n), resulting in overall O(n log n) time.

Q: What pattern does Boats to Save People use?

The Pattern: Two Pointers (Greedy Pairing) The Heuristic: Always attempt to pair the heaviest person with the lightest person who can fit with them; if not possible, send the heaviest alone. This greedy contraction reduces the problem size optimally in linear time.

Problem

Given an array people where people[i] is the weight of the ith person and an integer limit representing the maximum weight a boat can carry, return the minimum number of boats required to carry every person, where each boat can carry at most two people and their combined weight must be at most limit.

1 ≤ people.length ≤ 5 * 10⁴
1 ≤ people[i] ≤ limit ≤ 3 * 10⁴

Example

Input: people = [3,2,2,1], limit = 3

Output: 3

Sort the array to get [1,2,2,3]. The algorithm pairs the lightest (1) and heaviest (3) people. Since 1 + 3 = 4 > limit (3), they cannot share a boat, so the heaviest person (3) goes alone. Next, the two 2s can share a boat since 2 + 2 = 4 > limit, so each goes alone. The lightest person (1) pairs with one 2, but since 1 + 2 = 3 <= limit, they share a boat. The total boats used is 3.

Approach

Straightforward Solution

A brute-force approach tries all pairs to find valid combinations, resulting in O(n^2) time, which is too slow for large inputs.

Core Observation

The problem reduces to pairing the heaviest person with the lightest person possible without exceeding the limit, to minimize the total number of boats.

Path to Optimal

Preview

Sorting the array allows a two-pointer approach: one pointer at the lightest person, one at the heaviest. If their combined weight fits in one boat, pair them and move both pointers; otherwise, the heaviest person goes alone, and only the right pointer moves…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort the people array. Initialize two pointers: left at start, right at end…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Sorting the array takes O(n log n), and the two-pointer traversal is O(n), resulting in overall O(n log n) time.

Space

O(1)

The algorithm uses only a few variables for pointers and counters, with no additional data structures proportional to input size.

Solution

Python

1class Solution:
2    def numRescueBoats(self, people: list[int], limit: int) -> int:
3        people.sort()
4
5        left = 0
6        right = len(people) - 1
7        boat_count = 0
8
9        while left <= right:
10            if people[left] + people[right] <= limit:
11                left += 1
12
13            right -= 1
14            boat_count += 1
15
16        return boat_count

Step-by-Step Solution

1

Sort People to Enable Efficient Pairing

3	`people.sort()`

Objective

To arrange people in ascending order of weight, facilitating the two-pointer pairing strategy.

Key Insight

Sorting is essential because it allows the algorithm to efficiently pair the lightest and heaviest people by moving pointers inward. Without sorting, pairing decisions would require expensive searches or checks, increasing complexity.

Interview Quick-Check

Core Logic

Sorting enables the two-pointer technique by ordering weights, so the lightest and heaviest candidates can be paired greedily.

Complexity

Sorting dominates the time complexity at O(n log n), which is acceptable given the problem constraints.

2

Initialize Two Pointers and Boat Counter

To set up pointers at both ends of the sorted array and a counter to track the number of boats used.

3

Greedily Pair Lightest and Heaviest People to Minimize Boats

To iterate through the array, pairing the heaviest person with the lightest if possible, and counting boats accordingly.

4

Return Total Number of Boats Required

To output the minimum number of boats calculated after processing all people.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 3 Critical

people.sort()

Sort the people array in ascending order.

Sorting enables the two-pointer approach by ordering weights, allowing efficient pairing of the lightest and heaviest individuals to minimize boats.

Line 10 Critical

if people[left] + people[right] <= limit:

Check if the lightest and heaviest person can share a boat.

This conditional determines if pairing is possible, maximizing boat utilization by combining two people when their weights fit the limit.

Line 13 Critical

right -= 1

Move right pointer backward to assign the heaviest person a boat.

The heaviest person always occupies a boat in each iteration, so the right pointer moves inward to exclude them from further consideration.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does pairing the heaviest person with the lightest possible person guarantee a minimal number of boats?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Boats to Save People from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Boats to Save People drill

or drill a free problem

1	`class Solution:`
2	`def numRescueBoats(self, people: list[int], limit: int) -> int:`
3	`people.sort()`
4
5	`left = 0`
6	`right = len(people) - 1`
7	`boat_count = 0`
8
9	`while left <= right:`
10	`if people[left] + people[right] <= limit:`
11	`left += 1`
12
13	`right -= 1`
14	`boat_count += 1`
15
16	`return boat_count`