LeetCode Largest Rectangle in Histogram: Increasing Stack

Overview

LeetCode Largest Rectangle in Histogram: Linear time approach can be derived based on Increasing Stack, why it works is explained in detail and code is given.

LeetCode Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution and Precautions: Increasing Stack

This is quite a difficult problem. You can find the same problem in POJ as well. And the final elegant solution would involve a quite advanced data structure called Increasing Stack, now let’s try to tackle this problem step by step:

(1) O(N^3) approach: for every pair of bars i, j, find its area of the rectangle using i as the left bound and j as the right bound. To calculate the area, one needs to find the shortest bar between i and j, so the total time would be O(N^2) * O(N) which is O(N^3)

(2) O(N^2) approach: one don’t have to scan the bars between i and j every time to find the shortest bar in approach (1). One can always keep a the current shortest bar and each time use const time to update this value. So the time complexity would be reduced as O(N^2). This still cannot work efficiently to pass LeetCode OJ for this Largest Rectangle in Histogram problem, but we can think about it a bit further, there are actually lot of unnecessary computations, as we know, if height[i] > height[i-1], then there is not need to check all the cases of rectangles with height[i-1] being its right bound, this gives a heuristic to prune the search space, based on this, the following code (although the time complexity is still O(N^2) ) can actually pass the LeetCode OJ for this Largest Rectangle in Histogram problem:

public class Solution {
    public int largestRectangleArea(int[] height) {
        int maxRect = 0;
        for (int i = 0, len = height.length; i < len; ++i) {
            while (i + 1 < len && height[i] <= height[i+1])
                ++i;

            int h = height[i];
            for (int j = i; j >= 0; --j) {
                h = Math.min(h, height[j]);
                maxRect = Math.max(maxRect, h * (i - j + 1));
            }
        }
        return maxRect;
    }
}

And we also get a key fact we will utilize in the next linear time approach based on increasing stack. The key fact is:

only “peak” histogram can be the left or right bound where a “peak” histogram is defined as the the one h[i] and h[i] > h[i+1] AND h[i] > h[i-1] if any

(3) O(N) approach: Note the second approach is a naive try to utilize the key fact above, the smartest way to utilize the fact is by using an increasing stack and follow a bit different angle: The idea is that, each bar say H defines a maximum rectangle which use this bar H as the shortest histogram in it. H **defines this maximum rectangle by finding the both the first left and the first right side bar to **H which is shorter than** H. **If we can find the left and right bounds for each bar in linear time, then another linear scan could give us the global maximum rectangle by find the maximum value over height[i] * (rightbound[i]l – leftbound[i] – 1).

Increasing stack is such a data structure helping us to find all the bounds in linear time.  For example, to find the right bound for each bar i (the right bound of i is just the index of the first bar shorter than bar i on the right side of i), we continue to push the histogram into the stack until we get a shorter histogram (we call this shorter histogram as the current histogram) than the one on the top of the stack. Ok, obviously, this shorter one is the right bound of the top histogram. We then keep poping the stack until we get a histogram which is shorter than the current histogram (now we can stop because if we push the current histogram we will not break the increasing property of this increasing stack data structure). All the popped out histogram will use the current histogram as their right bound (think about it, this is correct). We repeat this process, until all the histogram are pushed into the stack. Finally, we need to clear the stack, and set the right bound of the remaining histograms in that stack. Since each histogram is just pushed and popped once, this process cost O(N) time. Similarly, we can get the left bounds. Then a third linear scan will give us the global maximum rectangle as previously discussed. The following code is a further simplified version and I will explain more about it for you to understand:

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stk = new Stack<Integer>();
        int maxArea = 0;
        for (int i = 0, len = height.length; i < len; ++i) {
            if (stk.empty() || height[i] >= height[stk.peek()]) {
                stk.push(i);
            }
            else {
                int shortest = stk.pop();
                int leftBound = stk.empty() ? 0 : stk.peek() + 1;
                maxArea = Math.max(maxArea, height[shortest] * (i - leftBound));
                --i;
            }
        }

        int curr = height.length;
        while (!stk.empty()) {
            int shortest = stk.pop();
            int leftBound = stk.empty() ? 0 : stk.peek() + 1;
            maxArea = Math.max(maxArea, height[shortest] * (curr - leftBound));
        }
        return maxArea;
    }
}

The code above actually simulate the algorithm process just described: For each popped out histogram (let’s call it shortest), we try to calculate the area of the largest rectangle containing this popped out one (shortest) by treating it as the shortest histogram, and we only need to know the left and right bound as we discussed, since we maintain the increasing stack, we can get the left and right bound in constant time, the right bound is obvious, it is just the current one we encountered but why the left bound is the previous stack.top() one? Here is why: Because those histograms which are already popped out within the [leftBound, shortest) must be taller than or equal to shortest, by the property of increasing stack, only when encountering a shorter histogram as the shortest one here, will all those histograms within [leftBound, shortest] will be popped out!

Remarks: There are O(NlogN) approach by utilizing another advanced data structure called segment tree, I haven’t tried out the detailed algorithms yet and I will update it when that one is investigated.

Summary

LeetCode Largest Rectangle in Histogram: Linear time approach can be derived based on Increasing Stack, why it works is explained in detail and code is given.

Written on May 16, 2013