- You are given a number n, representing the size of array a.
- You are given n numbers, representing the height of bars in a bar chart.
- You are required to find and print the area of the largest rectangle in the histogram.
Space Complexity: O(n)
Let's take an array to understand the problem. arr = [6,2,5,4,5,1,6].
Now, if we consider the rectangle of height 4 and spanned between index 2 till 4.
This way we can create rectangles and we will have to find the rectangle with the largest area.
What we can do is for every number to try to extend towards the left as much as possible and try to extend towards the right as much as possible such that the height of the bars is at least the height of the current bar.
Now, what are these left and right extremes? These are nothing but the next smaller element to the right and the next smaller element to the left. If the NSE to the right is r and NSE to the left is l then the width of the rectangle is r-l-1. For example, in the above drawing, the NSE to the left is 1 and that of to the right is 5. So 5-1-1 = 3 which is the width of the rectangle. And the height is the value of the current element. So the area is 3*4 = 12.
But what if there is no next smaller element to the right and left. Like, take the value at index 1. It has no smaller elements to the left. We will assume the NSE to left for index 1 to be -1. And consider the value at index 6, it has no NSE to right. For that, we will consider the value to be arr.length i.e in this case 7. This will save us some extra conditions.
Now you know the code for NSE to the left and right. Use that and the logic we discussed to get the answer.
- Iterate through the string and :
- Refer to the code for NSE index to the right and create an array.
- Refer to the code for NSE index to the left and create an array.
- Iterate through the given array.
- the width will be right index - left index + 1
- the height is a[index]
- so the area is height*width, if it's greater than the existing maxArea it becomes the new maxArea.
If you faced any difficulty to understand how the code works you can look at the dry runs in the video from
Calculating NSE is O(n) we already know that. And to calculate the maximum area we are just doing a single loop. Hence that too results in O(n).
We are just using stacks for calculating the NSEs but for the maximum area we are not using any auxiliary space, so the space complexity will still be O(n)