LESSON 323 OF 414 · STACK

Largest Rectangle in Histogram in Scala: O(n) with a Stack

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

The number of bars is between 1 and 10⁵
0 <= heights[i] <= 10⁴

STEP 1 OF 18

Guided

Ctrl + Enter to check

SCALA · STACK

Largest Rectangle In Histogram in Scala, explained

Problem overview

The method largestRectangleArea receives an Array[Int] named heights. Each element is the height of a bar, and every bar is one unit wide. The method returns the area of the largest rectangle that fits inside the bars, where the rectangle's sides run along the bars and its base sits on the axis.

For heights = Array(2, 1, 5, 6, 2, 3) the answer is 10. The bars at indices 2 and 3 have heights 5 and 6, so a rectangle of height 5 and width 2 fits over them: 5 * 2 = 10. For Array(2, 4) the answer is 4, either as a rectangle of height 4 and width 1 or as one of height 2 and width 2.

The input can have up to 100,000 bars with heights up to 10,000, so a method that tries every pair of left and right ends, which takes O(n^2) time or worse, is too slow.

Approach: the bar that limits the rectangle

Every rectangle is limited by its shortest bar. So instead of choosing a left end and a right end, choose the limiting bar i and ask how far a rectangle of height heights(i) can stretch. It can stretch left and right as long as the neighbouring bars are at least as tall as bar i. It stops at the nearest bar on each side that is strictly lower.

That gives two numbers per bar: left(i), the index of the nearest lower bar on the left, and right(i), the index of the nearest lower bar on the right. The widest rectangle of height heights(i) covers the indices strictly between them, so its width is right(i) - left(i) - 1. The answer is the maximum of heights(i) * (right(i) - left(i) - 1) over all bars.

Finding the nearest lower bar for every index could cost O(n) each, which would be O(n^2) in total. A stack does it in O(n) overall. While scanning from left to right, the stack holds the indices of bars that have not met a lower bar yet. Their heights never decrease from bottom to top. When bar i arrives, every bar on top of the stack that is taller than heights(i) has just found its nearest lower bar on the right: it is i. Pop those bars, record i for them, then push i. A scan from right to left with the same code finds the nearest lower bar on the left.

Step by step

Store the length in n, since it is used many times.
Create left with Array.fill(n)(-1). The value -1 means "no lower bar on the left", as if a bar of height 0 stood before index 0.
Create right with Array.fill(n)(n). The value n means "no lower bar on the right", as if a bar of height 0 stood after the last index. The formula for the width then works at both borders without special cases.
Create the stack as an empty mutable.Stack[Int].
Scan left to right and call removeAndUpdate(heights, stack, right, i) for each index. Bars that are still on the stack at the end have no lower bar to their right, so their entries in right keep the value n.
Clear the stack so the second scan starts from nothing.
Scan right to left over (0 until n).reverse and call the same helper with left. The helper doesn't care about the direction: it compares heights(i) with the bars waiting on the stack.
Compute the answer. Start a var answer at 0 and, for each index, keep the larger of the current answer and heights(i) * (right(i) - left(i) - 1).
Return answer as the last expression.
The helper removeAndUpdate loops while the stack is not empty and heights(i) is less than the height of the bar on top. In each pass it writes i into arr for the top index, which is the nearest lower bar of that index, and pops it. After the loop it pushes i.

The solution in Scala

class Solution {
    def removeAndUpdate(heights: Array[Int], stack: mutable.Stack[Int], arr: Array[Int], i: Int): Unit = {
        while (stack.nonEmpty && heights(i) < heights(stack.top)) {
            arr(stack.top) = i
            stack.pop()
        }
        stack.push(i)
    }

    def largestRectangleArea(heights: Array[Int]): Int = {
        val n = heights.length
        val left = Array.fill(n)(-1)
        val right = Array.fill(n)(n)

        val stack = mutable.Stack[Int]()
        for (i <- 0 until n) {
            removeAndUpdate(heights, stack, right, i)
        }

        stack.clear()
        for (i <- (0 until n).reverse) {
            removeAndUpdate(heights, stack, left, i)
        }

        var answer = 0
        for (i <- 0 until n) {
            answer = math.max(answer, heights(i) * (right(i) - left(i) - 1))
        }

        answer
    }
}

For heights = Array(2, 1, 5, 6, 2, 3) the two arrays end up as:

left  = -1, -1, 1, 2, 1, 4
right =  1,  6, 4, 4, 6, 6

For bar 2 (height 5), the nearest lower bars are at indices 1 and 4, so the width is 4 - 1 - 1 = 2 and the area is 10. Bar 1 (height 1) reaches both borders: its width is 6 - (-1) - 1 = 6, so its area is 6. The maximum over all six bars is 10.

Scala details:

Array.fill(n)(value) has two parameter lists. The first gives the size and the second gives the element. The element expression is evaluated once per slot, which doesn't matter for a constant.
mutable.Stack is a mutable collection. The short name relies on import scala.collection.mutable at the top of the file. push adds on top, top reads the top without removing it, and pop() removes and returns it. Calling top on an empty stack throws an exception, which is why the loop condition tests stack.nonEmpty first: && stops at the first false operand.
The helper changes the caller's objects. Arrays and the stack are objects, so removeAndUpdate writes into the caller's own right or left and stack, not into copies. That is why it can return Unit.
(0 until n).reverse gives the indices n - 1 down to 0. The range 0 until n excludes n.
Last expression. The method ends with answer and needs no return.
No overflow. Int is 32 bits and wraps silently, but the largest possible area is 10,000 * 100,000 = 1,000,000,000, which fits below 2,147,483,647.

Complexity

Time: O(n). Each index is pushed once and popped at most once in each scan, so the two scans cost O(n) in total even though the helper contains a loop. The final loop is O(n) too.

Space: O(n). The arrays left and right and the stack each hold at most n numbers.

Edge cases and common mistakes

A single bar. Array(5) gives 5. Nothing is lower, so left(0) is -1, right(0) is 1, and the width is 1 - (-1) - 1 = 1.
A bar of height 0. Array(0, 9, 0) gives 9. The zero bars split the histogram, and a zero-height bar contributes an area of 0.
Equal heights. Array(3, 3, 3) gives 9. The loop pops only strictly taller bars, so equal bars stay on the stack and left and right keep their border values. Every bar then computes the full width of 3. Popping on <= instead would record an equal neighbour as a "lower" bar and cut rectangles short, so keep the strict comparison.
Sorted heights. Array(1, 2, 3, 4, 5) and Array(5, 4, 3, 2, 1) both give 9, from 3 * 3.
Wrong border values. The width formula right(i) - left(i) - 1 assumes -1 and n as the "none" values. Starting left at 0 or right at n - 1 makes bars that reach a border one unit too narrow.
Not clearing the stack between the scans leaves old indices behind, and the second scan then compares against bars it should never see.

Testing

Array(2, 1, 5, 6, 2, 3) returns 10.
Array(2, 4) returns 4.
Array(2, 1, 2) returns 3, from the bar of height 1 spanning all three positions.
Array(3, 3, 3) returns 9.
An array of 100,000 elements all equal to 10,000 returns 1,000,000,000.

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

Start learning free