{"id":10045,"date":"2022-09-27T10:20:29","date_gmt":"2022-09-27T10:20:29","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10045"},"modified":"2022-10-10T09:28:41","modified_gmt":"2022-10-10T09:28:41","slug":"largest-rectangular-area-in-histogram-set-2-2","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/largest-rectangular-area-in-histogram-set-2-2\/","title":{"rendered":"Largest rectangular Area in Histogram – Set 2"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h3>\n

You will be given an array<\/a> that represents a histogram. The values of the array represent the height of the bars of the histogram and the width of each bar will be 1. You have to find the maximum area of a rectangle that can be drawn in that histogram.<\/p>\n

Example<\/h3>\n

Consider the following array and the histogram corresponding to it.<\/p>\n

\"\"<\/p>\n

The shaded region shows the maximum area rectangle that is there in the histogram.<\/p>\n

Brute Force Approach<\/h3>\n

Let us consider the array and histogram shown below.<\/p>\n

\"\"<\/p>\n

We start from the first bar of this histogram. We can see that the width of this bar cannot be extended on the left side as there is no element to its left and on the right side too, it can\u2019t be extended as the bar on its right is smaller than it. <\/p>\n

Hence, the maximum area possible fir this bar is height width = 2<\/em>1 = 2.<\/p>\n

\"\"<\/p>\n

Now, we move to the next bar. Here, we can extend its width on the left and right sides both as the bars are greater in height. This is shown below. <\/p>\n

\"\"<\/p>\n

So, the current rectangular area becomes height width = 1 <\/em> 7 =7. Also, this will be the current maximum.<\/p>\n

\"\"<\/p>\n

Now, we move to the 3rd bar. Here, the width can be extended as shown below. <\/p>\n

\"\"<\/p>\n

So, the current area will be 5 * 2 = 10. This is also the current maximum.<\/p>\n

\"\"<\/p>\n

So, we can keep doing this procedure till we complete the array traversal. The maximum area for this histogram is 10 only.<\/p>\n

However, finding the extent to which we can extend the width for each bar will take O(N) time. Also, we have to do this for all the N bars. This means that the time complexity of this solution will become O(N2). So, let us think of some better ways to solve the problem.<\/p>\n

Optimized Approach<\/h3>\n

We can see that the width of a bar can be extended till all the bars next to it are greater than it. The other way to put this is we extend the width of a bar till we find the \u201cNext Smaller Bar\u201d or the \u201cNext Smaller Element\u201d. <\/p>\n

\"\"<\/p>\n

You can see the case shown above. The index of the next smaller element to the left of index 4 is 1. Also, the index of the next smaller element to the right of index 4 is 6. So, if we call the index of the next smaller element to the right R and the index of the next smaller element to the left L, the width becomes = R – L – 1.<\/p>\n

So, this is what we were doing in the above approach too. How can we optimize it? Well, we were traversing at each bar or at each index at a time to calculate the next smaller element to the left and right. If we use an efficient algorithm to find the next smaller element and find it before calculating the area, we can just traverse the array once again, and since we would have calculated the Next Smaller Elements on both sides already, we would be able to calculate the area of each index in O(1) time which means the total solution will be O(N) and we know that we can find the NSE to the left and right using Stack in O(N) time.<\/p>\n

You have studied the Celebrity Problem where we learned how to calculate the next greater element to the left and right. We have to apply the same logic here. It is just that the next greater element would be replaced by the next smaller element.<\/p>\n

Important:<\/h4>\n

If there is no Next Smaller Element to the Right for any element, we consider the index = arr.length as the Next Smaller Element for that element. Similarly, if there is no Next Smaller Element to the left, consider index 0 as the NSE to the left.<\/p>\n

Now that we have understood the approach, let us write the code for the same.<\/p>\n

Code Implementation<\/h4>\n\t\t\t\t\t\t