LESSON 295 OF 348 · HEAP

Minimum Number of Boats in Kotlin: Sorting and a Stack of Partners

Practice O(n log n) Read the full explanation

You are given an array weights where weights[i] is the weight of the i^th student, and an infinite number of boats where each boat can carry a maximum weight of maxWeight. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most maxWeight and the absolute difference of their weights shouldn't exceed maxDiff.

Return the minimum number of boats to carry every given student.

Example 1:

Input: weights = [2, 4, 2, 1], maxWeight = 6, maxDiff = 1
Output: 3
Explanation: 3 boats: (1, 2), (2) and (4)

Example 2:

Input: weights = [81, 37, 32, 88, 55, 93, 45, 72],
    maxWeight = 100, maxDiff = 10
Output: 6
Explanation: 6 boats (81), (37, 32), (88), (55, 45), (93), (72)

STEP 1 OF 14

Guided

Ctrl + Enter to check

KOTLIN · HEAP

Minimum Number Of Boats in Kotlin, explained

Problem overview

You have an IntArray weights with one weight per student and as many boats as you like. A boat carries one or two students. Two students may share a boat only if

their combined weight is at most maxWeight, and
the difference between their weights is at most maxDiff.

The function returns the smallest number of boats that carries everyone.

With weights = [2, 4, 2, 1], maxWeight = 6 and maxDiff = 1 the answer is 3: the students weighing 1 and 2 share a boat, and the other 2 and the 4 each go alone. The 4 can't pair with a 2, since the difference of 2 is larger than maxDiff.

With [81, 37, 32, 88, 55, 93, 45, 72], maxWeight = 100 and maxDiff = 10 the answer is 6, from the pairs (37, 32) and (55, 45) plus four students alone.

Approach

Every boat that carries two students saves one boat compared with sending everyone alone. So the task is to form as many valid pairs as possible: with n students and p pairs the answer is n - p.

A greedy strategy works on the sorted weights. Take the heaviest student first. Heavy students have the fewest possible partners, because the sum limit is the hardest for them to meet. Give each one the heaviest partner that is allowed, since that partner is also the one with the fewest options among the lighter students. The code follows exactly this order.

The difficulty is finding that partner quickly. A partner must satisfy two conditions at once:

sum: weights[p] + weights[i] <= maxWeight, which holds for the lighter students up to some point;
difference: weights[i] - weights[p] <= maxDiff, which holds for the heavier of them.

As i goes down through lighter students, the sum limit only gets looser, so the set of students allowed by the sum only grows. The pointer p moves right once through the sorted array and collects them. Among the collected students the heaviest is the closest in weight to i, and the code keeps them in a stack where the heaviest is on top.

Step by step

Sort weights in ascending order with weights.sort().
Counters. answer counts the boats and p is the index of the next light student to consider. Both are vars that start at 0.
Taken students. isTaken is a HashSet of indices of students who already have a partner.
The stack. stack is an ArrayList<IntArray> of pairs (weight, index). Weights are pushed in ascending order, so the last one pushed is always the heaviest, and a plain stack does the job of a max heap here.
Heaviest first. The loop runs i from weights.size - 1 down to 0 using downTo.
Collect candidates by sum. While p < i and weights[p] + weights[i] <= maxWeight, student p fits with i by weight. Since later i values are lighter, this student keeps fitting, so each student is pushed once.
Push. Add intArrayOf(weights[p], p) to the stack and increment p.
Skip taken students. If i is in isTaken, it already shares a boat with a heavier student that was counted, so continue.
Look for a partner. The next while loop runs while the stack is not empty and the top's weight is within maxDiff of weights[i]. If even the top, the closest in weight, is too far away, every other candidate is too.
Discard unusable tops. Read the top into top. If top[1] == i (the student is the candidate itself) or the candidate is in isTaken, pop it and continue.
Pair them. Otherwise add both i and top[1] to isTaken, pop the top and break.
Count the boat. After the search, answer++. It runs once for a student alone and once for a pair, because the partner is skipped later in step 8.
Return answer after the loop.

The solution in Kotlin

class Solution {
    fun minBoats(weights: IntArray, maxWeight: Int, maxDiff: Int): Int {
        weights.sort()
        var answer = 0
        var p = 0
        val isTaken = HashSet<Int>()
        val stack = ArrayList<IntArray>()
        for (i in weights.size - 1 downTo 0) {
            while (p < i && weights[p] + weights[i] <= maxWeight) {
                stack.add(intArrayOf(weights[p], p))
                p++
            }
            if (isTaken.contains(i)) continue
            while (stack.isNotEmpty() && weights[i] - stack[stack.size - 1][0] <= maxDiff) {
                val top = stack[stack.size - 1]
                if (top[1] == i || isTaken.contains(top[1])) {
                    stack.removeAt(stack.size - 1)
                    continue
                }
                isTaken.add(i)
                isTaken.add(top[1])
                stack.removeAt(stack.size - 1)
                break
            }
            answer++
        }
        return answer
    }
}

Kotlin details worth knowing:

weights.sort() sorts the IntArray in place and returns Unit. The caller's array changes. sorted() would return a new List and leave the array alone.
for (i in weights.size - 1 downTo 0) counts down and includes both ends. A normal range such as 0..n would be empty if it were written backwards.
stack[stack.size - 1] reads the last element of the ArrayList and removeAt(stack.size - 1) removes it. Each element is an IntArray of two numbers, [0] for the weight and [1] for the index.
The continue inside the inner while repeats that while loop, not the outer for. The continue after isTaken.contains(i) is outside the inner loop and goes to the next i.
Kotlin has no int/Integer split in the source: HashSet<Int> holds boxed values, but contains compares by value.

Complexity

Time: O(n log n). Sorting costs O(n log n). After that, the pointer p moves at most n times and every student is pushed once and popped at most once, so the main loop is O(n) with constant-time set and list operations on average.

Space: O(n). The stack and the set can each hold up to n entries. sort() works in place on the array.

Edge cases and common mistakes

Nobody can pair. If maxDiff is small or weights are close to maxWeight, each student takes a boat and the answer is weights.size.
Only the sum limit. With a large maxDiff the difference check never stops the search, and the problem becomes the classic two-pointer boats problem.
Empty array. The loop never runs and the result is 0.
Counting both students of a pair. The pair is one boat. That's the reason a partner is recorded in isTaken and skipped when its turn comes.
Forgetting the top[1] == i check. A student can be on the stack and still be the one currently being placed, and must not be paired with itself.
Leaving weights unsorted. Both the pointer p and the "top is the heaviest" idea depend on the ascending order.

Testing

[2, 4, 2, 1] with maxWeight = 6, maxDiff = 1 returns 3.
[81, 37, 32, 88, 55, 93, 45, 72] with maxWeight = 100, maxDiff = 10 returns 6.
An empty array returns 0.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free