Problem overview
The method minBoats receives the students' weights, a boat limit maxWeight and a limit maxDiff. Boats are unlimited, and each carries one or two students. Two students can share a boat only if their weights add up to at most maxWeight and their weights differ by at most maxDiff. The method returns the smallest number of boats that carries everyone.
In the first example, weights = [2, 4, 2, 1], maxWeight = 6 and maxDiff = 1. The students 1 and 2 can share a boat, since 1 + 2 = 3 and the difference is 1. The other 2 can't pair with 4, because their difference is 2. The result is 3 boats: (1, 2), (2) and (4). The second example has eight students and needs 6 boats.
Approach: heaviest student first
With only the weight limit, the classic greedy idea is to sort the students and pair the heaviest remaining one with the lightest one. The extra maxDiff rule breaks that: the lightest student may be too far from the heaviest in weight, and the best partner is instead the heaviest student who still fits.
So the lesson sorts the weights in ascending order and goes through the students from the heaviest to the lightest. For each student not yet seated, it looks for a partner among the lighter students who fit by total weight, and picks the heaviest of them, as long as the difference is at most maxDiff. If no one qualifies, that student rides alone. Each seated student is remembered, so nobody is counted twice.
To find the candidates quickly, a pointer p starts at the lightest student and moves right over the sorted weights. Every student the pointer passes fits with the current heavy student by total weight. Because later heavy students are lighter, they fit with them too, so a student is pushed once and stays valid. The candidates sit on a stack. They are pushed in ascending weight order, so the top is always the heaviest candidate, the closest in weight to the current student. A plain array with push and pop does the job that a max heap would do, because the pushes are already sorted.
On [1, 2, 2, 4] (sorted) with maxWeight = 6 and maxDiff = 1: the weight 4 sees all three lighter students as candidates, but the top, a 2, is 2 away, which is above the limit, so the 4 rides alone. The next 2 pairs with the other 2 (difference 0). The remaining 1 finds only itself on the stack and rides alone. That is 3 boats.
Step by step
- Sort
weightsin ascending order. - Declare
answerandp, both 0: the boat count, and the pointer over the light end. - Create the set
isTakenfor the students who already share a boat with a heavier one. - Create the stack. It is an array of
[number, number]pairs, each holding a weight and its index. - Loop
ifrom the last index down to 0, from the heaviest student to the lightest. - Push the candidates. A
whileloop runs whilep < iandweights[p] + weights[i] <= maxWeight. - Push
[weights[p], p]and incrementp. Each student enters the stack only once. - Skip students already seated: if
isTakenhasi,continue, because that boat was counted when the heavier partner was handled. - Search for a partner while the stack isn't empty.
- Read the top pair into
[topWeight, topIndex]without removing it. - Stop if the top is too far in weight. If
weights[i] - topWeight > maxDiff,break. The top is the closest candidate, so every other one is even further. The pair stays on the stack, because a lighter student later might be close enough to it. - Pop the top and, if it is the student
iitself or is already taken,continueto the next candidate. - Seat the pair: add both
iandtopIndextoisTaken, thenbreak. - Count the boat with
answer++after the search. It is counted whether studentifound a partner or not. - Return
answerafter the main loop.
The solution in TypeScript
class Solution {
minBoats(weights: number[], maxWeight: number, maxDiff: number): number {
weights.sort((a, b) => a - b);
let answer = 0, p = 0;
const isTaken = new Set<number>();
const stack: [number, number][] = [];
for (let i = weights.length - 1; i >= 0; i--) {
while (p < i && weights[p] + weights[i] <= maxWeight) {
stack.push([weights[p], p]);
p++;
}
if (isTaken.has(i)) continue;
while (stack.length > 0) {
const [topWeight, topIndex] = stack[stack.length - 1];
if (weights[i] - topWeight > maxDiff) {
break;
}
stack.pop();
if (topIndex === i || isTaken.has(topIndex)) {
continue;
}
isTaken.add(i);
isTaken.add(topIndex);
break;
}
answer++;
}
return answer;
}
}
The TypeScript details worth a closer look:
- Sorting numbers needs a comparator.
sort()with no argument compares values as strings, so[10, 9, 1].sort()gives[1, 10, 9]. The comparator(a, b) => a - bsorts numerically in ascending order. sortchanges the array in place. The caller'sweightsarray ends up sorted. Copy it first with[...weights]if you still need the original order.- A tuple type.
[number, number][]is an array of pairs, each with exactly two numbers. At run time the pairs are plain two-element arrays. - Destructuring.
const [topWeight, topIndex] = stack[stack.length - 1];reads the last pair into two variables. The pair stays in the stack, because indexing doesn't remove anything. - The last element is
stack[stack.length - 1]. An empty array has no last element, which is why thewhileloop checksstack.length > 0first. - A one-line
ifwithout braces, as inif (isTaken.has(i)) continue;, is legal, but the braces version is easier to extend safely.
Complexity
Time: O(n log n). Sorting costs O(n log n). The main loop is linear: p only moves right, so each student is pushed at most once, and each pair is popped at most once, so the two inner loops together do O(n) work. A pair that causes a break before the pop stays on the stack, and that happens at most once per student i.
Space: O(n). The stack and the set can each hold up to n entries.
Edge cases and common mistakes
- No students. The loop doesn't run and the method returns 0.
- One student. The stack stays empty, and the answer is 1.
- Nobody can pair. If
maxDiffis 0 and all weights are different, every student rides alone and the answer isweights.length. - Equal weights. Two students of weight 3 with
maxWeight = 6and anymaxDiffshare a boat, since the difference is 0. - Pairing a student with themselves. The stack can hold the student's own entry, which is why the code skips
topIndex === i. - Counting a boat for a seated student. The
isTakencheck keeps the heavier partner's boat from being counted twice. - Forgetting the weight total. The difference rule alone isn't enough: students 40 and 45 differ by only 5, but with
maxWeight = 80they don't fit together. - Sorting without a comparator. A default
sort()would order weights like 100, 20, 3 as text and break every later step.
Testing
weights = [2, 4, 2, 1],maxWeight = 6,maxDiff = 1gives3.weights = [81, 37, 32, 88, 55, 93, 45, 72],maxWeight = 100,maxDiff = 10gives6.weights = []gives0.weights = [7],maxWeight = 10,maxDiff = 1gives1.