Problem overview
The method minBoats receives the students' weights, weights, and two limits, maxWeight and maxDiff. There are unlimited boats. A boat carries one student alone, or two students if their combined weight is 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 (sum 3, difference 1). The 4 can't share with a 2, because the difference of 2 is too big. So the answer is 3: one pair and two single students. In the second example, [81, 37, 32, 88, 55, 93, 45, 72] with maxWeight = 100 and maxDiff = 10 needs 6 boats, with only the pairs (37, 32) and (55, 45).
Approach: place the heaviest first
Every boat saved is a pair, so the goal is as many pairs as possible. Sort the weights, then handle students from the heaviest down. The heaviest student has the strictest requirements: the partner must be light enough to fit by total weight, and close enough in weight to satisfy maxDiff.
Among the students who fit with the current student i by total weight, the best partner is the heaviest one. The lighter the partners are, the more likely they are too far from i in weight. The heaviest fitting partner is also the closest in weight, so if even that one is more than maxDiff away, no other candidate is within reach, and i sails alone.
To find that partner quickly, a second index p moves right over the sorted weights. For each i, every student at a position p < i with w[p] + w[i] <= maxWeight is pushed on a stack. Weights are pushed in ascending order, so the top of the stack is always the heaviest candidate. A student who fits with the current i also fits with every later, lighter i, so each student is pushed once. The stack does the job a max heap would do, at lower cost.
Step by step
- Sort. Parameters in Swift are constants, so store
weights.sorted()in a new constantwand usewfrom here on. - Counters. Declare
answerandpwithvar, both starting at 0. - Taken set. Create the empty set
isTakenof indices that have already been paired with a heavier student. - Candidate stack. Create
stackas an array of(Int, Int)tuples holding a weight and an index. - Loop from the heaviest. Iterate
iwithstride(from: w.count - 1, through: 0, by: -1). The wordthroughincludes 0;towould stop before it. - Collect candidates. A
whileloop runs as long asp < iandw[p] + w[i] <= maxWeight. - Push them. Inside, append
(w[p], p)tostackand incrementp. - Skip paired students. If
isTakencontainsi,continue. This student already has a boat, so no new boat is counted. - Look for a partner. A
whileloop runs as long as the stack is not empty andw[i] - stack[stack.count - 1].0 <= maxDiff. The top is the heaviest waiting candidate. - Discard unusable tops. Read the top into
top. Iftop.1 == iorisTaken.contains(top.1), remove the last element andcontinue: the top is either the student himself or already paired. - Pair them. Otherwise insert both
iandtop.1intoisTaken. - Consume the candidate. Remove the last element of
stackandbreak. - Count the boat. After the inner loop, increment
answer. One boat is used fori, with or without a partner. - Return
answerafter the main loop.
The solution in Swift
class Solution {
func minBoats(_ weights: [Int], _ maxWeight: Int, _ maxDiff: Int) -> Int {
let w = weights.sorted()
var answer = 0, p = 0
var isTaken = Set<Int>()
var stack = [(Int, Int)]()
for i in stride(from: w.count - 1, through: 0, by: -1) {
while p < i && w[p] + w[i] <= maxWeight {
stack.append((w[p], p))
p += 1
}
if isTaken.contains(i) { continue }
while !stack.isEmpty && w[i] - stack[stack.count - 1].0 <= maxDiff {
let top = stack[stack.count - 1]
if top.1 == i || isTaken.contains(top.1) {
stack.removeLast()
continue
}
isTaken.insert(i)
isTaken.insert(top.1)
stack.removeLast()
break
}
answer += 1
}
return answer
}
}
The Swift details worth a closer look:
sorted()againstsort().sorted()returns a new sorted array and leavesweightsalone.sort()sorts in place and works only on avar.- Counting down. The C-style
forloop doesn't exist in Swift, and(0..<n).reversed()would also work. Herestride(from:through:by:)with a step of-1says where to start, where to end (inclusive) and which way to go. For an empty array the start is -1, so the loop doesn't run. - Tuples.
(w[p], p)is an(Int, Int)tuple, and its parts are read as.0and.1. A stack of tuples avoids a separate struct for two numbers. - An array as a stack.
appendpushes,removeLast()pops, andstack[stack.count - 1]reads the top. Reading the top of an empty array crashes, which is why every read follows a!stack.isEmptycheck. - Short
ifon one line. Swift requires braces even for a one-statementif, soif isTaken.contains(i) { continue }keeps them.
Complexity
Time: O(n log n). Sorting costs O(n log n). After that, p only moves right, each student is pushed once and popped at most once, and every other step is constant time on average, so the main loop is O(n).
Space: O(n). The sorted copy, the stack and the set each hold at most n entries.
Edge cases and common mistakes
- Empty list. The loop doesn't run and the method returns 0.
- One student.
[5]withmaxWeight = 6returns 1. - Equal weights.
[3, 3]withmaxWeight = 6andmaxDiff = 0returns 1: the difference is exactly 0, which is allowed. - Two ways to fail.
[3, 4]withmaxWeight = 6needs 2 boats, because 3 + 4 is over the limit. WithmaxWeight = 10andmaxDiff = 0it also needs 2, because the weights differ. - Forgetting the difference rule. A solution that only looks at the total weight would pair 1 and 4 in the first example and return 2, which is wrong.
- Counting paired students twice. A student already in
isTakenmust not add a boat when its turn comes. - Using
to:instead ofthrough:. The lightest student, at index 0, would never be visited.
Testing
weights = [2, 4, 2, 1],maxWeight = 6,maxDiff = 1gives3.weights = [81, 37, 32, 88, 55, 93, 45, 72],maxWeight = 100,maxDiff = 10gives6.weights = [],maxWeight = 6,maxDiff = 1gives0.weights = [3, 3],maxWeight = 6,maxDiff = 0gives1.weights = [3, 4],maxWeight = 6,maxDiff = 5gives2.
