Programming Interview 39: Find Largest Rectangle Size in a Histogram in linear time

Step by step to crack Programming Interview questions Q39: Find Largest Rectangle Size in a Histogram in linear time.
E.g. in histogram {2,4,2,1}, the largest rectangle starts from 1st until 3rd with height of 2. The largest size is thus 6.

Solution:
Use Stack to keep track of height and start indexes
Compare current height with previous one

#1: current Larger than previous (top of height stack)
Push current height & index as candidate rectangle start position

#2: current EQUALS previous
Ignore, as largest rectangle will start from previous with same height

#3: current is less than previous
Need keep popping out previous heights, and compute the candidate rectangle with height and width (current index MINUS previous index)
Push the height and index (appropriate position) to stacks

[bhavukmathur]

One modification makes the code correct -
When you pop the elements, save the index of the last popped element. Then, when you push the new element, make the index of that element as the index of the last popped element..

For eg - For array as 6, 2, 5, 4, 5, 1, 6
When 4 comes, 5 is popped out. This time, push (4) with the index of popped (5). This will give the correct result.

[abocidejofa]

whoever is doing these soundless videos, you are simply amazing. thank you very much. I started watching your videos a few days ago. I will keep watching. I definitely will learn a lot from you. God bless you.

[ziruizhang]

for every element, it will be pushed in and pop out at most once, so the time complexity is O(2*n)

[AI_Edu_]

It should be linear. You may think about the worst case you keep pushing and poping all the time, that results in 2*N time, because each index will be pushed and popped or calculated once.

[JohnQiao]

There is a very simple approach to this question. Start to traverse the array on the both sides ( left = 0, right = array.length - 1)

Because the container's area is decided by the shorter one, case 1: array[left] < array[right], there will be no j < right that can make a greater area from 'left' to 'j'. So we advance left by 1 (left++). case 2: array[right] >= array[left], similar to case 1.

 written in Java

[subhadeepmaji]

This solution seems to be incorrect ..consider for example the second block to be of height 3 instead of 4 then the largest area rectangle ending at index 2 starts at index 1 and not 2 because its area is 2*2 while index 2 starting rectangle is 3*1 .

[sahilk]

Wrong algorithm, does not work with simple case :6, 2, 5, 4, 5, 1, 6
Answer should be 12
According to algorithm it is 8

[sunnypavan]

how about storing only the indexes and refer the values from the indexes stored in stack