Boats to Save People

Explanation & Solution

Description

Given an array people where people[i] is the weight of the ith person, and an infinite number of boats each with a maximum weight limit, return the minimum number of boats to carry every person.

Each boat carries at most two people at the same time, provided the sum of their weights does not exceed limit.

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

Output: 1

Explanation: 1 boat can carry both people (1 + 2 = 3 which equals the limit).

Constraints

1 <= people.length <= 5 * 10⁴
1 <= people[i] <= limit <= 3 * 10⁴
Each person can fit in a boat by themselves (i.e., people[i] <= limit)

Approach

Two Pointers pattern

1. Sort the Array

Sort people in ascending order
This allows us to pair the lightest person with the heaviest person efficiently

2. Initialize Two Pointers and a Counter

Set left = 0 (lightest person)
Set right = people.length - 1 (heaviest person)
Set boats = 0 to count the total number of boats used

3. Try to Pair the Lightest with the Heaviest

While left <= right, check if the lightest remaining person and the heaviest remaining person can share a boat
If people[left] + people[right] <= limit, they fit together — move left++ to mark the lighter person as boarded

4. The Heaviest Always Boards

Regardless of whether a pair was formed, the heaviest person boards the current boat
Decrement right-- and increment boats++

5. Continue Until All People Are Assigned

The loop ends when left > right, meaning everyone has been placed on a boat
Return boats as the answer

Key Insight

The greedy strategy works because pairing the lightest with the heaviest is always optimal. If the lightest person cannot fit with the heaviest, then no one else can either, so the heaviest must ride alone. This greedy pairing minimizes wasted capacity across all boats.

Time

O(n log n)dominated by the sort step

Space

O(1)only pointer variables are used (ignoring sort space)

Visualization

Input:

[1, 2], limit = 3

—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone

3 steps

Solution Code

4Sum