LESSON 299 OF 348 · STACK

Largest Rectangle in Histogram in Kotlin: O(n) with Two Stack Passes

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:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

STEP 1 OF 18

Guided

Ctrl + Enter to check

KOTLIN · STACK

Largest Rectangle In Histogram in Kotlin, explained

Problem overview

You get an IntArray heights, the heights of the bars in a histogram. Every bar is 1 unit wide. The function returns the area of the largest rectangle that fits inside the histogram, where the rectangle is made of neighbouring bars and its height is limited by the shortest bar it covers.

For [2, 1, 5, 6, 2, 3] the answer is 10: the bars of heights 5 and 6 are neighbours, so a rectangle of height 5 and width 2 fits over them, and 5 x 2 = 10. For [2, 4] the answer is 4, from either the single bar of height 4 or the rectangle of height 2 and width 2.

The constraints allow up to 10^5 bars with heights up to 10^4, so the algorithm has to be close to linear.

Approach

Every rectangle is limited by its shortest bar. That gives a way to check all candidates without listing them: take each bar in turn and treat it as the shortest bar of the rectangle. The widest rectangle of height heights[i] stretches left and right until it reaches a bar that is lower than heights[i]. If you know

left[i], the index of the nearest lower bar to the left, and
right[i], the index of the nearest lower bar to the right,

then the rectangle covers the bars strictly between them. Its width is right[i] - left[i] - 1 and its area is heights[i] * (right[i] - left[i] - 1). The answer is the maximum over all i.

Checking every bar by walking left and right costs O(n^2) in the worst case. The nearest lower bar is the same kind of question as "next greater element", and a stack answers it for all bars in a single pass, O(n) in total.

Step by step

The size. n holds heights.size, since the code uses it many times.
The left answers. left is an IntArray(n) filled with -1. The value -1 means "no lower bar on the left", as if a bar of height 0 stood just before the first index.
The right answers. right is filled with n, which means "no lower bar on the right": a virtual bar of height 0 just past the end. n can't be confused with a real index.
The stack. stack is an ArrayDeque<Int> that holds the indices of bars still waiting for their nearest lower bar. Their heights never decrease from bottom to top.
Left-to-right pass. For each i from 0 to n - 1, call the helper removeAndUpdate(heights, stack, right, i). Scanning rightwards, the first lower bar an index meets is its nearest lower bar on the right, so the answers go into right.
Reset. stack.clear() empties the stack. Indices left on it in the first pass have no lower bar to their right, so their entries in right stay n. The variable is a val, but its contents can still be cleared.
Right-to-left pass. Loop with i from n - 1 downTo 0 and call removeAndUpdate(heights, stack, left, i). Scanning leftwards, the same helper finds the nearest lower bar on the left.
Best area. answer starts at 0 and, for every i, becomes maxOf(answer, heights[i] * (right[i] - left[i] - 1)).
Return answer.

The helper

removeAndUpdate sits inside the Solution class next to largestRectangleArea. Its parameters are the heights, the stack, the array to fill (arr, which is either left or right) and the index i:

While the stack is not empty and heights[i] is less than the height of the bar whose index is on top, bar i is the first lower bar that the top index has met.
Set arr[stack.last()] = i, then pop that index with removeLast().
When the loop ends, push i with addLast so it waits for its own answer.

The loop pops only strictly taller bars, so bars of equal height stay on the stack. That's fine: an equal bar is not lower, so it doesn't stop a rectangle, and the rectangle may extend over it.

The solution in Kotlin

class Solution {
    fun removeAndUpdate(heights: IntArray, stack: ArrayDeque<Int>, arr: IntArray, i: Int) {
        while (stack.isNotEmpty() && heights[i] < heights[stack.last()]) {
            arr[stack.last()] = i
            stack.removeLast()
        }
        stack.addLast(i)
    }

    fun largestRectangleArea(heights: IntArray): Int {
        val n = heights.size
        val left = IntArray(n) { -1 }
        val right = IntArray(n) { n }

        val stack = ArrayDeque<Int>()
        for (i in 0 until n) {
            removeAndUpdate(heights, stack, right, i)
        }

        stack.clear()
        for (i in n - 1 downTo 0) {
            removeAndUpdate(heights, stack, left, i)
        }

        var answer = 0
        for (i in 0 until n) {
            answer = maxOf(answer, heights[i] * (right[i] - left[i] - 1))
        }

        return answer
    }
}

Kotlin details worth knowing:

Arrays and the deque are objects, and Kotlin passes references to them. The helper changes the caller's own arr and stack, not copies. The helper has no return type, so it returns Unit.
The same helper serves both directions because it does not care which way the loop runs: it only compares heights[i] with the bars waiting on the stack.
0 until n excludes n; n - 1 downTo 0 counts down and includes both ends.
IntArray(n) { n } uses the lambda to fill every position with n.
In the helper's loop condition, stack.isNotEmpty() comes first so that stack.last(), which throws on an empty deque, is never reached on an empty stack.
The area is an Int. With the largest allowed input, 10^5 bars of height 10^4, it is 10^9, which fits within the Int limit of about 2.1 billion.

Complexity

Time: O(n). Each of the two passes pushes every index once and pops it at most once, so each pass is O(n). The final loop is O(n) as well.

Space: O(n). The left and right arrays and the stack each take up to n entries.

Edge cases and common mistakes

A single bar. For [0] the answer is 0; for [7], left[0] is -1 and right[0] is 1, so the width is 1 and the area is 7.
Equal bars. For [3, 3, 3] no bar is lower than another, so every bar gets the full width 3 and the answer is 9.
Off-by-one in the width. The nearest lower bars are not part of the rectangle, which is why the width is right[i] - left[i] - 1.
Wrong defaults. The values -1 and n stand for imaginary bars of height 0 outside the array. Using 0 and n - 1 would shrink the width of rectangles that reach the edges.
Forgetting stack.clear(). Indices from the first pass would leak into the second pass and produce wrong left values.

Testing

[2, 1, 5, 6, 2, 3] returns 10.
[2, 4] returns 4.
[3, 3, 3] returns 9.
[0] 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