Largest Area in a Histogram

Problem Statement : 
      Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

In the above histogram width of each bar is 1 and heights are H = [2, 1, 5, 6, 2, 3]. 


Solution: 

By brute force algorithm, we can consider each bar every time and consider all other bars adjacent to it which are equal or greater and find the area by Height of the bar multiplied by right and left index difference plus one

Area = Bar Height * (right_index - left_index + 1)

The time complexity for this case would be (n^2) i.e. n-squared. 

We would be discussing another optimised technique which will have a complexity of O(n) using stack. 


We would essentially use same trick as we had done in the Brute force but with storage in a stack we will find a better optimised solution, The trick is to compute left and right index of the of bar such that all bars between these indices are either equal or greater than the bar in consideration. 

Traverse all the bars from left to right and push the bar to the stack if the stack is empty or if the bar is greater than the top of the stack. Once the next incoming bar is smaller than the top of the stack, anchor the index here and this would act as right_index start. Pop the bar and calculate the area as the smallest bar for this left index would be the updated top in the stack. 
i.e. A = bar_height * (right_index - 1 -  new_top_index). 

If this is slightly confusing then lets write the algorithm for it. 

Algorithm :
1. Create a empty stack. 
2. Push i , if stack is empty or H[i] is greater than stack.peek()
3. If the bar is small set anchor to i, continue to pop the indces from the stack until H[stack.peek()] is smaller H[i], for each element poped calculate the area evert time you pop element using 

A = bar_height(of the poped index) * (i - 1 - stack.peek()) 

when stack is empty, 
A = bar_height(of the poped index) * i

update Area A if the newly computed Area is greater than previous. 

4. If all the items are over and stack is still not empty repeat process 3.

Code below :

Let me know if you have any questions in the comments section or any feedback.
Happy Coding !! :)