Boats to Save People

1. Define the problem

You are given an array people where people_i is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit. Return the minimum number of boats to carry every given person. Sort the array, then run converging two pointers : always take the heaviest remaining person, pairing them with the lightest remaining person if they fit together, otherwise the heaviest goes alone.

Constraints

1 ≤ people.length ≤ 5 × 10⁴
1 ≤ people_i ≤ limit ≤ 3 × 10⁴

Example

Inputpeople = [3, 2, 2, 1], limit = 3

Output3

Explanation Sorted: [1, 2, 2, 3]. The heaviest person (3) cannot pair with anyone within the limit, so takes a boat alone; the next heaviest (2) pairs with the lightest (1) for exactly 3; the remaining person (2) takes the last boat alone — 3 boats total.

2. Visualize the solution

Converge two pointers, always placing the heaviest person

Statusinit

Sorted: [1, 2, 2, 3]. left=1 (idx 0), right=3 (idx 3): sum = 4 > limit(3) — the heaviest goes alone. boats = 1.

What happens in this step

left = 0 (value 1), right = 3 (value 3)
sum = 1 + 3 = 4, limit = 3

4 > limit, so the pair doesn't fit. Only right moves inward, from index 3 to index 2; the heaviest person takes a boat alone. boats = 1.

Step 1 of 4

Steps to visualize

Sort the array so the lightest and heaviest people are at opposite ends.
Compare the lightest remaining person (left) and the heaviest remaining person (right).
If their combined weight fits within the limit, they share a boat — move both pointers inward.
Otherwise the heaviest person takes a boat alone — move only the right pointer inward.
Either way, one boat is used each iteration; stop once the pointers cross.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Converge two pointers, always placing the heaviest person

Statusinit

Sorted: [1, 2, 2, 3]. left=1 (idx 0), right=3 (idx 3): sum = 4 > limit(3) — the heaviest goes alone. boats = 1.

What happens in this step

left = 0 (value 1), right = 3 (value 3)
sum = 1 + 3 = 4, limit = 3

4 > limit, so the pair doesn't fit. Only right moves inward, from index 3 to index 2; the heaviest person takes a boat alone. boats = 1.

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function numRescueBoats(people, limit) {
  const sorted = [...people].sort((a, b) => a - b);
  let left = 0;
  let right = sorted.length - 1;
  let boats = 0;

  while (left <= right) {
    if (sorted[left] + sorted[right] <= limit) {
      left++;
    }
    right--;
    boats++;
  }

  return boats;
}

Time: O(n log n)
Space: O(n) (for the sort)

5. Test cases

Test cases

Input	Expected	Covers
`people = [3, 2, 2, 1], limit = 3`	`3`	example from the docstring
`people = [1, 2, 2, 3], limit = 4`	`2`	everyone fits into pairs
`people = [3, 3, 3, 3], limit = 3`	`4`	nobody can pair up, so everyone needs their own boat
`people = [5], limit = 5`	`1`	smallest valid input: a single person
`people = [1, 2, 3, 4], limit = 5`	`2`	pairs that sum to exactly the limit
`people = [3, 3, 3, 3, 3], limit = 6`	`3`	an odd count of duplicate weights, leaving one person solo

Boats to Save People