Maximize the rectangular area under Histogram

Question

I have a histogram with integer heights and constant width 1. I want to maximize the rectangular area under a histogram. e.g.:

 _ | | | |_  |   | |   |_ |     | 

The answer for this would be 6, 3 * 2, using col1 and col2.

O(n^2) brute force is clear to me, I would like an O(n log n) algorithm. I'm trying to think dynamic programming along the lines of maximum increasing subsequence O(n log n) algo, but am not going forward. Should I use divide and conquer algorithm?

PS: People with enough reputation are requested to remove the divide-and-conquer tag if there is no such solution.

After mho's comments: I mean the area of largest rectangle that fits entirely. (Thanks j_random_hacker for clarifying :) ).

Answer 1

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