LESSON 319 OF 414 · HEAP

Minimum Number of Boats in Scala: Sorting, Two Pointers and a Stack

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

SCALA · HEAP

Minimum Number Of Boats in Scala, explained

Problem overview

The method minBoats receives the students' weights, a boat capacity maxWeight and a limit maxDiff. Boats are unlimited, and each carries one or two students. Two students may share a boat only if their weights add up to at most maxWeight and differ by at most maxDiff. The method returns the smallest number of boats that carries everyone.

For weights = [2, 4, 2, 1], maxWeight = 6 and maxDiff = 1, the answer is 3. The student of weight 4 can't pair with anyone, because even the closest weight, 2, differs by 2. The 1 and a 2 fit together, and the remaining 2 rides alone, or the two 2s share a boat and the 1 rides alone. Either way, three boats. For the second example, with eight students, maxWeight = 100 and maxDiff = 10, the answer is 6.

Approach: heaviest first, closest lighter partner

Every pair that shares a boat saves one boat, so the goal is to form as many valid pairs as possible. The answer is the number of students minus the number of pairs.

The solution sorts the weights and processes students from the heaviest to the lightest. For the current student i, the best partner is a lighter student who fits by total weight and whose weight is as close to weights(i) as possible, since closeness is what the maxDiff rule measures. Candidates are collected on a stack: a second pointer p starts at the lightest student and moves right while weights(p) + weights(i) <= maxWeight, pushing each student it passes. Because p moves over the sorted array in ascending order, the last student pushed is the heaviest candidate, so the top of the stack is the closest in weight to weights(i). If the top is too far away (a difference above maxDiff), every other candidate is too.

A candidate pushed for one student still fits the next one, because the next student is lighter or equal, so the sum can only shrink. That is why p never has to move back, and each student is pushed at most once.

Traced on the sorted weights [1, 2, 2, 4] with maxWeight = 6 and maxDiff = 1:

i = 3 (weight 4): p pushes the weights 1, 2 and 2, since each sums to at most 6 with the 4. The top is a 2, which is 2 below the 4, more than maxDiff. The 4 gets its own boat.
i = 2 (weight 2): the top of the stack is this student itself, which is thrown away. The next top, the 2 at index 1, is a valid partner. Both are marked as taken, and one boat is counted.
i = 1: already taken, so it is skipped.
i = 0 (weight 1): the only candidate left on the stack is itself, so it is discarded and it gets its own boat.

That is three boats.

Step by step

Sort weights in ascending order.
Declare answer and p as vars set to 0. p is the pointer that feeds the stack from the light end.
Create isTaken, an empty mutable Set[Int] of indices of students who already have a partner.
Create stack, an ArrayBuffer[(Int, Int)] of (weight, index) pairs. Pushes come in ascending weight, so a plain stack does the work of a max heap here.
Walk from the heaviest student: var i = weights.length - 1 and while (i >= 0). The loop decrements i itself.
Feed the stack. An inner while runs as long as p < i && weights(p) + weights(i) <= maxWeight.
Push (weights(p), p) onto stack and increment p.
Skip students already paired. If isTaken.contains(i), just decrement i. Scala has no continue, so everything else goes in the else branch.
Look for a partner. In the else branch declare var done = false, a flag that replaces the missing break, and loop while !done, the stack is non-empty and weights(i) - stack(stack.size - 1)._1 <= maxDiff.
Discard useless tops. Read the top into val top. If top._2 == i || isTaken.contains(top._2), remove the last element of the stack.
Pair up otherwise. Add both i and top._2 to isTaken.
Finish the search. Remove the last element of the stack and set done = true.
Count the boat. Below the inner loop, increment answer and decrement i. A pair counts once, at its heavier student; the lighter one is skipped later.
Return answer as the last expression.

The solution in Scala

class Solution {
    def minBoats(weights: Array[Int], maxWeight: Int, maxDiff: Int): Int = {
        scala.util.Sorting.quickSort(weights)
        var answer = 0
        var p = 0
        val isTaken = scala.collection.mutable.Set[Int]()
        val stack = scala.collection.mutable.ArrayBuffer[(Int, Int)]()
        var i = weights.length - 1
        while (i >= 0) {
            while (p < i && weights(p) + weights(i) <= maxWeight) {
                stack += ((weights(p), p))
                p += 1
            }
            if (isTaken.contains(i)) {
                i -= 1
            } else {
                var done = false
                while (!done && stack.nonEmpty && weights(i) - stack(stack.size - 1)._1 <= maxDiff) {
                    val top = stack(stack.size - 1)
                    if (top._2 == i || isTaken.contains(top._2)) {
                        stack.remove(stack.size - 1)
                    } else {
                        isTaken.add(i)
                        isTaken.add(top._2)
                        stack.remove(stack.size - 1)
                        done = true
                    }
                }
                answer += 1
                i -= 1
            }
        }
        answer
    }
}

The Scala details worth a closer look:

Sorting changes the caller's array. scala.util.Sorting.quickSort(weights) sorts an Array[Int] in place and returns Unit. After minBoats runs on [2, 4, 2, 1], the caller's array reads [1, 2, 2, 4]. Copy the array first, with weights.clone(), if the original order matters.
Tuples. (weights(p), p) is a pair of type (Int, Int), read back with ._1 and ._2, which count from 1. In stack += ((weights(p), p)), the inner parentheses build the tuple and the outer ones are the call to +=.
An ArrayBuffer as a stack. The last element is the top: stack(stack.size - 1) reads it and stack.remove(stack.size - 1) pops it, both in constant time. nonEmpty needs no parentheses.
The mutable set. scala.collection.mutable.Set[Int]() is named in full because the default Set is immutable. add returns a Boolean that the code ignores.
No break or continue. The done flag and the else branch do their jobs.

Complexity

Time: O(n log n). Sorting costs O(n log n). Afterwards each student is pushed at most once, because p only moves forward, and removed from the stack at most once. The index i moves down by one per iteration. All set operations take constant time on average. The sweep is therefore O(n).

Space: O(n). The stack and the set each hold at most n entries.

Edge cases and common mistakes

No students. The main loop doesn't run, so the answer is 0.
One student. [5] returns 1: nobody else is available.
Weight fits but difference doesn't. [1, 5] with maxWeight = 6 and maxDiff = 1 returns 2, but with maxDiff = 4 it returns 1.
Difference fits but weight doesn't. [3, 4] with maxWeight = 6 and maxDiff = 5 returns 2, since 3 + 4 is 7.
Equal weights. [3, 3] with maxWeight = 6 and maxDiff = 0 returns 1. A student must never pair with themselves, which is why the code compares top._2 with i.
Counting a boat for the lighter partner. The lighter student is skipped through isTaken. Counting it again would give one boat too many for every pair.
Using the lightest student as everyone's partner. It satisfies the weight limit but may break maxDiff. The stack keeps the closest valid weight instead.
Relying on the original order. The method reorders its argument, as described above.

Testing

weights = [2, 4, 2, 1], maxWeight = 6, maxDiff = 1 gives 3.
weights = [81, 37, 32, 88, 55, 93, 45, 72], maxWeight = 100, maxDiff = 10 gives 6.
weights = [1, 5], maxWeight = 6, maxDiff = 4 gives 1.
weights = [3, 4], maxWeight = 6, maxDiff = 5 gives 2.
weights = [], maxWeight = 6, maxDiff = 1 gives 0.

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

Start learning free