Maximize the rectangular area under Histogram

The above answers have given the best O(n) solution in code, however, their explanations are quite tough to comprehend. The O(n) algorithm using a stack seemed magic to me at first, but right now it makes every sense to me. OK, let me explain it.

First observation:

To find the maximal rectangle, if for every bar x, we know the first smaller bar on its each side, let’s say l and r, we are certain that height[x] * (r - l - 1) is the best shot we can get by using height of bar x. In the figure below, 1 and 2 are the first smaller of 5.

OK, let’s assume we can do this in O(1) time for each bar, then we can solve this problem in O(n)! by scanning each bar.

Then, the question comes: for every bar, can we really find the first smaller bar on its left and on its right in O(1) time? That seems impossible right? … It is possible, by using a increasing stack.

Why using an increasing stack can keep track of the first smaller on its left and right?

Maybe by telling you that an increasing stack can do the job is not convincing at all, so I will walk you through this.

Firstly, to keep the stack increasing, we need one operation:

while x < stack.top():
    stack.pop()
stack.push(x)

Then you can check that in the increasing stack (as depicted below), for stack[x], stack[x-1] is the first smaller on its left, then a new element that can pop stack[x] out is the first smaller on its right.

Still can’t believe stack[x-1] is the first smaller on the left on stack[x]?

I will prove it by contradiction.

First of all, stack[x-1] < stack[x] is for sure. But let’s assume stack[x-1] is not the first smaller on the left of stack[x].

So where is the first smaller fs?

If fs < stack[x-1]:
    stack[x-1] will be popped out by fs,
else fs >= stack[x-1]:
    fs shall be pushed into stack,
Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x].

Therefore stack[x-1] must be the first smaller.

Summary:

Increasing stack can keep track of the first smaller on left and right for each element. By using this property, the maximal rectangle in histogram can be solved by using a stack in O(n).

Congratulations! This is really a tough problem, I’m glad my prosaic explanation didn’t stop you from finishing. Attached is my proved solution as your reward 🙂

def largestRectangleArea(A):
    ans = 0
    A = [-1] + A
    A.append(-1)
    n = len(A)
    stack = [0]  # store index

    for i in range(n):
        while A[i] < A[stack[-1]]:
            h = A[stack.pop()]
            area = h*(i-stack[-1]-1)
            ans = max(ans, area)
        stack.append(i)
    return ans