Largest Rectangle Area histogram

This arguement is the same as the largest Rectangle in a histogram.

" Benjamin Franklin Young Man’s Best Companion, in which Franklin wrote, "Remember that time is money."[1]"

This questions is simple requesting us to find the largest area in histogram with continues heights.

arr = [8, 2, 6, 9, 7, 2]

consider his arrays as the heights of the histogram:

> if we traverse from left to right ->>> index 0
> 
> 8 > 2 so it cannot extablish a consistent area=8. we move to index 1
> 
> 2 < \[6,9,7,2==2\] and also less than 8 index so the area = 2\*6=12
> 
> from index 2 -->
> 
> 6>2 so we cannot traverse back
> 
> 6< \[9,7\] so we can have an area =6\*3=18
> 
> from index 3-->
> 
> 9>6 so we cannot traverse back and also >7 so we cannot traverse forward area=9
> 
> from index 4-->
> 
> 7> 2 we cannot traverse forward but
> 
> 7<\[9\] so we can traverse one time back area = 2\*7=14
> 
> last index 5-->
> 
> 2 is the last index so we can cannot traverse forward
> 
> but 2<\[8, 2==2, 6, 9, 7\] so we can traverse all back to start area =2\*6=12

NOTE: THE LARGEST AREA WAS 18

This can be achieved with the brute force method below

def LargestrectangleinHistogram(arr):
    arr = [8, 2, 6, 9, 7, 2]
    mx = -1 * 10 ** 10
    for i in range(len(arr)):
        for j in range(i, len(arr)):

            H = min(arr[i:j + 1])
            W = j - i + 1
            mx = max(mx, H * W)

    return mx


if __name__ == '__main__':
    print(LargestrectangleinHistogram([]))

The complexity is O(n^2). Which is the worse case in this algorithm.

Can we Improve this?

. Yes .

With DP or minimization method we still need to loop(n*n) for the right area? 😓

So we use a stack. Which is going to give us a linear time.

if a stack is pop and appended() then the complexity becomes linear.

def largestRectAreaHistogram(arr):
    arr = [8, 2, 6, 9, 7, 2]
    stk, mx = [], -1 * 10 ** 9

    for i, val in enumerate(arr + [0]):
        while stk and arr[stk[-1]] > val:
            H = arr[stk.pop()]
            if not stk:
                W = i
            else:
                W = i - stk[-1] - 1
            mx = max(mx, W * H)

        stk.append(i)
    return mx


if __name__ == '__main__':
    print(largestRectAreaHistogram([]))

Complexity of O(n)

Consider the stack solution above . We have an empty stack and all the array(heights) of histogram is pushed.

Only pop when the stack is not empty and when the top value of the stack is equals current height

    for i, val in enumerate(arr + [0]):
        while stk and arr[stk[-1]] > val:

the height of the current histogram is what we have on top of the array stack.

  H = arr[stk.pop()]

how many we have in stack determines the number of heights we travelled.

And maximum area is determined but the multiplication of the current histogram and the width it travelled.

            H = arr[stk.pop()]
            if not stk:
                W = i
            else:
                W = i - stk[-1] - 1
            mx = max(mx, W * H)

NOTE

when we finish looping the array, there is a chance the top is finished but the last item added to the stack was not pop so we need to add an empty zero index at the end to take care of the issue.

  for i, val in enumerate(arr + [0]):

[Largest Area in Histogram]: Stack O(n) complexity | O(n^2) if time is not what we need