Last Updated on October 10, 2022 by Gokul Kannan
Problem Statement
You will be given an array 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.
Example
Consider the following array and the histogram corresponding to it.
The shaded region shows the maximum area rectangle that is there in the histogram.
Brute Force Approach
Let us consider the array and histogram shown below.
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’t be extended as the bar on its right is smaller than it.
Hence, the maximum area possible fir this bar is height width = 21 = 2.
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.
So, the current rectangular area becomes height width = 1 7 =7. Also, this will be the current maximum.
Now, we move to the 3rd bar. Here, the width can be extended as shown below.
So, the current area will be 5 * 2 = 10. This is also the current maximum.
So, we can keep doing this procedure till we complete the array traversal. The maximum area for this histogram is 10 only.
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.
Optimized Approach
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 “Next Smaller Bar” or the “Next Smaller Element”.
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.
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.
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.
Important:
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.
Now that we have understood the approach, let us write the code for the same.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
int getMaxArea(int arr[], int n)
{
stack<int> s;
s.push(-1);
int area = arr[0];
int i = 0;
vector<int> left_smaller(n, -1), right_smaller(n, n);
while(i<n){
while(!s.empty()&&s.top()!=-1&&arr[s.top()]>arr[i]){
right_smaller[s.top()] = i;
s.pop();
}
if(i>0&&arr[i]==arr[i-1]){
left_smaller[i] = left_smaller[i-1];
}else{
left_smaller[i] = s.top();
}
s.push(i);
i++;
}
for(int j = 0; j<n; j++){
area = max(area, arr[j]*(right_smaller[j]-left_smaller[j]-1));
}
return area;
}
int main()
{
int arr[] = {2, 1, 5, 6, 2, 3, 1};
int n = sizeof(arr )/sizeof(arr[0]);
cout << "maxArea = " << getMaxArea(arr, n) << endl;
return 0;
}
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
public static int getMaxArea(int arr[], int n)
{
Stack<Integer> s = new Stack<>();
s.push(-1);
int max_area = arr[0];
int leftSmaller[] = new int[n];
int rightSmaller[] = new int[n];
for (int i = 0; i < n; i++){
leftSmaller[i] = -1;
rightSmaller[i] = n;
}
int i = 0;
while (i < n)
{
while(!s.empty()&&s.peek()!=-1 && arr[i]<arr[s.peek()]){
rightSmaller[s.peek()] = (int)i;
s.pop();
}
if(i>0&&arr[i]==arr[(i-1)]){
leftSmaller[i] = leftSmaller[(int)(i-1)];
}else{
leftSmaller[i] = s.peek();
}
s.push(i);
i++;
}
for(i = 0; i<n; i++){
max_area = Math.max(max_area, arr[i]*(rightSmaller[i] - leftSmaller[i] - 1));
}
return max_area;
}
public static void main(String[] args)
{
int[] arr = {2, 1, 5, 6, 2, 3, 1};
System.out.println("Maximum area is " + getMaxArea(arr, arr.length));
}
}
Time Complexity
The time complexity of this solution is O(N) as we take O(N) time for each traversal of calculating the NSE to the left and right. Also, we take O(N) time to traverse the array to find the max area. So, the time complexity becomes O(N) + O(N) + O(N) = O(3N) = O(N).
Space Complexity
We use a stack to solve the problem which makes the space complexity O(N). Then, we have also used 2 auxiliary arrays storing the NSE to the left and right respectively. Hence the space complexity or auxiliary space is O(N).
We tried to discuss Largest rectangular area in histogram. We hope this article gives you a better understanding of Largest rectangular area in histogram, PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.