LESSON 324 OF 415 · STACK

Largest Rectangle in Histogram in Swift: 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

SWIFT · STACK

Largest Rectangle In Histogram in Swift, explained

Problem overview

The method largestRectangleArea receives an array heights. Each number 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' edges.

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. For [2, 4] the answer is 4, either from the bar of height 4 alone or from both bars at height 2.

Approach: find the nearest lower bar on each side

Look at the biggest rectangle and its shortest bar. The rectangle can't be taller than that bar, and it can't be extended sideways past a bar that is lower. So every candidate rectangle can be described like this: pick a bar i as the limiting height, then stretch as far left and right as the neighbours stay at least as tall as heights[i].

That stretch is bounded by two indices:

left[i], the index of the nearest bar on the left that is lower than heights[i], or -1 if there is none;
right[i], the index of the nearest lower bar on the right, or n if there is none.

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

Checking every bar by walking outwards until a lower bar appears costs O(n²) for a long staircase of bars. A stack makes it O(n). While scanning from left to right, the stack holds the indices of bars that haven't met a lower bar yet. Their heights never decrease from bottom to top. When a new bar is lower than the bar on top, that new bar is the first lower bar the top one has met, so the top bar's answer is known and it leaves the stack.

Take [2, 1, 5, 6, 2, 3]. Bar 0 (height 2) waits. Bar 1 (height 1) is lower, so bar 0 gets right[0] = 1, and bar 1 waits. Bars 2 and 3 are taller and join the stack. Bar 4 (height 2) is lower than 6 and 5, so right[3] = 4 and right[2] = 4; it stays above bar 1. Bar 5 joins. At the end, bars 1, 4 and 5 are still on the stack and keep the default right value, 6. A second pass from right to left, with the same helper, produces left: [-1, -1, 1, 2, 1, 4].

For bar 2 (height 5) the width is 4 - 1 - 1 = 2, and the area is 10.

Step by step

Store the count in n, since the bar count is needed many times.
Create left as a var array of n values, all -1. It is a var because the helper will change it.
Create right with n values, all n. The value n can never be a real index, so it means "no lower bar".
Create the stack st as an empty array of Int. Its end is the top.
Scan left to right. Each bar gives the helper a chance to settle the bars waiting on the stack.
Call the helper with right, because scanning in this direction finds the first lower bar to the right of each waiting bar.
Start over with an empty stack for the second pass.
Scan right to left with stride(from: n - 1, through: 0, by: -1), which includes index 0.
Call the same helper with left. Scanning from the right, the first lower bar a waiting index meets is its nearest lower bar on the left.
Keep the best area in answer, starting at 0.
Try every bar as the limiting height and apply the area formula with max.
Return answer.
Write the helper removeAndUpdate. It pops every waiting bar taller than heights[i], records i as that bar's lower neighbour in arr, and finally pushes i itself.

The solution in Swift

class Solution {
    func removeAndUpdate(_ heights: [Int], _ st: inout [Int], _ arr: inout [Int], _ i: Int) {
        while !st.isEmpty && heights[i] < heights[st.last!] {
            arr[st.last!] = i
            st.removeLast()
        }
        st.append(i)
    }

    func largestRectangleArea(_ heights: [Int]) -> Int {
        let n = heights.count
        var left = [Int](repeating: -1, count: n)
        var right = [Int](repeating: n, count: n)

        var st = [Int]()
        for i in 0..<n {
            removeAndUpdate(heights, &st, &right, i)
        }

        st = [Int]()
        for i in stride(from: n - 1, through: 0, by: -1) {
            removeAndUpdate(heights, &st, &left, i)
        }

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

        return answer
    }
}

Swift details worth a closer look:

inout and &. Arrays are value types: passing one to a function normally gives the function its own copy. Marking a parameter inout and writing &st at the call lets the helper change the caller's array. Without it the helper could not even assign to st or arr, because ordinary parameters are constants.
One helper, two directions. The helper never looks at the direction. It only compares heights[i] with the bars waiting on the stack, so the same code fills right in one pass and left in the other.
st.last!. last is an optional, nil for an empty array. The force-unwrap is safe only because !st.isEmpty is checked first in the same condition, and && stops evaluating when it is false.
[Int](repeating:count:). Builds an array with one value repeated, which is how left and right start with their defaults.
stride with through:. stride(from: n - 1, through: 0, by: -1) includes 0. With to: it would stop before 0, and n - 1 ..< 0 is not a valid range at all, because Swift traps when a range's upper bound is smaller than its lower bound. For n = 0 the stride is simply empty.
Strictly taller only. The loop pops bars that are strictly taller. Bars of equal height stay, so for [2, 2, 2] the bounds are left = [-1, -1, -1] and right = [3, 3, 3]: every bar reports the full width 3, and the area is 6.

Complexity

Time: O(n). In each pass every index is pushed once and popped at most once, so the while loop runs at most n times over the whole pass, not per bar. The two passes and the final loop each take linear time.

Space: O(n). left, right and the stack each hold up to n integers.

Edge cases and common mistakes

One bar. [5] gives left = [-1] and right = [1], so the width is 1 and the area is 5.
A zero-height bar. [0] gives 0. A zero also splits the histogram: no rectangle with positive height can cross it.
Equal heights. Popping with <= instead of < makes equal bars cut each other off. For [2, 2, 2] every width would become 1 and the method would return 2 instead of 6. The lesson's version keeps equal bars inside the stretch.
Forgetting the default bounds. Bars left on the stack at the end have no lower bar on that side. Their entries must stay -1 and n, which gives them the full width to the edge.
Off-by-one in the width. The bars at left[i] and right[i] are lower, so they are excluded. The width is right[i] - left[i] - 1, not right[i] - left[i].
Forgetting & or inout. Swift reports an error if an inout argument is passed without &, and a helper without inout can't assign to its parameters.

Testing

[2, 1, 5, 6, 2, 3] gives 10.
[2, 4] gives 4.
[2, 2, 2] gives 6.
[3, 1, 3, 2, 2] gives 6.
[5] gives 5, and [0] gives 0.

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

Start learning free