Maximum area of a rectangle in an histogram - Why do we need stack?

Question

Consider the following problem (and solution):

Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram.

The key idea is to calculate:

R[i] = Area of the largest rectangle with the bar at i is as the smallest bar in the rectangle (i.e. width = H[i]) left[i] = the left most boundary of R[i], which is the leftmost bar greater than H[i]. right[i] = the right most boundary of R[i], which is the rightmost bar greater than H[i].

I've understood that a stack is needed to calculate right and left but I think I was able to supply a similar solution without using a stack:

def max_area_rect(lst):
    n = len(lst)
    right = [-1] * n
    left = [-1] * n

    right[n - 1] = n
    for i in range(n - 2, -1, -1):
        right[i] = i + 1 if lst[i] > lst[i + 1] else right[i + 1]

    left[0] = -1
    for i in range(1, n):
        left[i] = i - 1 if lst[i - 1] < lst[i] else left[i - 1]

    max_res = -1
    for i in range(n):
        right_len = right[i] - i -1
        left_len = i - left[i] + 1
        h = min(lst[right_len - 1], lst[left_len + 1])
        res = (right_len + left_len) * h
        if res > max_res:
            max_res = res

    return max_res

    # test
    print(max_area_rect([4, 2, 1, 8, 6, 8, 5, 2])) # expected result: 20

So my question is: Why do we need a stack? Is my way valid?

No, this is not even close. Change the 5 to 6 and the output doesn't change. Change the 4 to 3 and the output changes to 15. The calculation that results in 20 is `res = (1 + 4) * 4`, which is completely wrong, but just happens to give the right answer. — user3386109, May 28 '18 at 08:10
Also, just feed your algorithm the same histogram in reverse: `[2, 5, 8, 6, 8, 1, 2, 4]`. Your code gives a result of 25. FWIW, you can find various solutions [here](https://stackoverflow.com/q/4311694/4014959). — PM 2Ring, May 28 '18 at 09:23

score 3 · Accepted Answer · answered May 28 '18 at 08:52

Definition of left[i] as you mentioned

left[i] = the left most boundary of R[i], which is the leftmost bar greater than H[i]

What you defined in code

left[i] = i - 1 if lst[i - 1] < lst[i] else left[i - 1]

i.e. if the bar to the left is higher, you are putting left[i] = left[i-1]. However, the mistake here is that the left[i-1] stores the leftmost index which is greater than lst[i-1] and not lst[i].

for example in sequence 6, 8, 5 in the input you gave, left[i] for 8 should not include 6, so left[i] should be i but left[i] for 5 should include 6 along with 8 and thats what your code is overlooking.

Maximum area of a rectangle in an histogram - Why do we need stack?

1 Answers1