Largest rectangle in histogram

Shreya Deep
Last Updated: May 16, 2022
Difficulty Level :
EASY

Introduction

A histogram represents a frequency distribution in form of rectangles whose widths (generally 1) represent class intervals and whose areas are proportional to the corresponding frequencies: the height of each is the average frequency density for the interval. Also, the rectangles are contiguous. 

In this article, we’ll learn how to find out the largest rectangle in a histogram.

Problem Statement

Given an array of integers, heights representing a histogram’s bar heights, return the area of the largest rectangle in that histogram. The rectangle here represents the rectangle formed by concatenating consecutive bars whose height is the minimum heights of all the bars in the rectangle and width is the number of bars. 

Note: The width of the bars is always 1.

For example: 

INPUT : heights = [2,1,5,6,2,3]

OUTPUT:  10

The largest rectangle will be with the 2nd and the 3rd bars (here, 0 indexed) combined. The area will be min(5,6)*2 = 10. 

INPUT : heights = [2,4]

OUTPUT:  4

The largest rectangle will be with both the bard combined. The area will be min(2,4)*2 = 4.

Recommended: Please try it on “CodeStudio” before moving on to the solution approach.

Approach 1: Brute force

We know that the height of the rectangle will be equal to the shortest bar included in it. Therefore, the idea is to for each bar, compute the maximal rectangle which includes that bar and the height of the rectangle is equal to the bar’s height (i.e. it is the shortest bar included). 

The brute method to implement the above idea is:

For each bar (of height h), find out how many bars on the immediate left are taller than h, say that is l. Similarly, find out how many bars in the immediate right are taller than h, say that is r.

Then, for the rectangle including this bar as its shortest bar, the width will be (r+l+1) and the height will be equal to the height of the shortest bar, h. Thus the area will be h*(r+l+1). Keep a variable for storing the maximum area and keep updating the variable whenever there is an area found with a greater value. 

We have to do this for each bar and keep updating the maximum area.

Steps are:

  • Input the number of bars.
  • Declare a vector to store the heights of the bars.
  • Input the values of the heights.
  • Call the largestRectangleArea function which return the required answer.
  • In the largestRectangleArea function:
    • Declare and initialize a variable "maxarea" to 0. This variable will store the maximum area of the rectangles.
    • Traverse through each bars in the heights vector. For each i from i=0 to i<n,
      • Take four variables, h, l, r, and area. “h” will denote the height of the current bar, l will represent the number of bars on the immediate left are taller than h, r will be the number of bars in the immediate right are taller than h and area will store the area of the rectangle will the current bar as the height.
      • When i==0, l will be 0 as there are no bars on the left of it. Calculate r, by running a loop from j=i+1 to j<n and check if height[j]>h, and increment r each time it is. 
      • When i==n-1, r will be 0 as there are no bars on the right of it. Calculate l, by running a loop from j=i-1 to i>=0 and check if height[j]>h, and increment l each time it is.
      • Otherwise, Calculate l and r separately. 
      • Calculate the area as h*(l+r+1).
      • Update the maxarea as max(maxarea,area)
      • Return maxarea.
      • Print answer.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

int largestRectangleArea(vector<int>&heights){
    int n = heights.size();
    int maxarea = 0;  // Declare and initialze a variable "maxarea" to 0. 
    //This variable will store the maximum area of the rectangles.
    for(int i=0;i<n;i++){  
        int h = heights[i]; // h is the height of that bar 
        int l,r,area; // l will store how many bars on the immediate left are taller than h
        // r will store how many bars in the immediate right are taller than h and area will store the area
        // of the rectangle will the current bar as the bar with minimum height.
        if(i==0){ // When i=0,
            r =0; 
            //Calculate r
            for(int j=i+1;j<n;j++){
                if(heights[j]>h){
                    r++;
                }
                else{
                    break;
                }
            }
            // l will be 0 as there are no bars on the left of it.
            l=0;
            area = h*(l+r+1);
        }
        else if(i==n-1){ // When i==n-1
            l=0;
            //Calculate l
            for(int j=i-1;j>=0;j--){
                if(heights[j]>h){
                    l++;
                }
                else{
                    break;
                }
            }
            // r will be 0 as there are no bars on the right of the current bar.
            r=0;
            area = h*(l+r+1);
        }
        else{
            l=0;
            r=0;
            // Calculate l
            for(int j=i-1;j>=0;j--){
                if(heights[j]>h){
                    l++;
                }
                else{
                    break;
                }
            }
            // Calculate r
            for(int j=i+1;j<n;j++){
                if(heights[j]>h){
                    r++;
                }
                else{
                    break;
                }
            }
            area = h*(l+r+1);
        }
        // Update maxarea to the maximum of maxarea and the current area.
        maxarea = max(maxarea,area);
    }
    // Return maxarea
    return maxarea;
}

int main()
{
    int n;
    cin>>n; //input the number of bars 
    vector<int>heights(n);  // Declare a vector to store the heights of the bars.
    for(int i=0;i<n;i++){
        cin>>heights[i];  // Input the values of the heights
    }
    int ans = largestRectangleArea(heights); // Call the largestRectangleArea  //function which returns the required answer
    cout<<ans<<endl;    //Print the answer.
    return 0;
}

Input

n=6, heights = [2,1,5,6,2,3]

Output

10

Complexities

Time complexity

O(n^2), where n is the number of bars.

Reason: For each index, we’re calculating the l and r values. Traversing each index takes O(n). Calculation of l and r takes another O(n) in the worst case. Thus, the complexity will be O(n^2).

Space complexity

O(1)

Reason: We’re aren’t creating any space other than those of the variables. Those take only O(1) time.

Approach 2: Optimization using stack

In the above implementation, for each bar, we do O(n) amount of work by scanning to the left and right. We need to think about how to optimize finding l and r.

When we’re at index i:

If the index of the first element to the left of the current bar(say, at index i) which has a height smaller than h (say lIndex). If the index of the first element to the right of the current bar which has a height smaller than h (say rIndex). 

Now, note that l is the same as (i-lIndex-1) ans similarly, r is the same as (rindex-i-1).Thus, if we can find llndex and rIndex for all the index in O(n) once, and then traverse the vector once and find the area, that will be a much efficient solution.

So, the discussion boils down to finding lIndex and rIndex for each i, in O(n) time.

For this, what we can do is, we can store the IIndexes of all the indexes in an array called lIndex. The same goes for rIndex. 

For example, if we have the array as [1,14,12,10,4]. 

Suppose we know the previous smaller element of 1,14,12,10. For 10, the previous smaller element is 1. 

Do we need to iterate over the entire array to figure out the previous smaller element for 4?

No!

  • We know that the element on the immediate left of 4 i.e. 10 > 4. Thus, 10 is not the previous smaller element for 4.
  • We also know that the previous smaller element of 10 is 1. So, we don’t need to compare 4 with 12 and 14, because we already know that everything between 10 and 1 is greater than 10 and hence also greater than 4.

We were able to skip over 14 and 12 because there’s no point in looking at elements that are bigger than 10.

Basically, instead of iterating through each element, we can skip elements by jumping over to the previous smaller elements. When we encounter an element say X which is greater than the current element, everything to the left of X that is greater than X is meaningless since they’ll never be the previous smaller element for the current element.

We can implement the above idea using a stack.

Steps are:

  • Input the number of bars.
  • Declare a vector to store the heights of the bars.
  • Input the values of the heights.
  • Call the largestRectangleArea function which returns the required answer.
  • In the largestRectangleArea function:
    • First check for a few base cases:  if the size of the heights vector is 0, return 0 as the answer because there are no rectangles possible. If the size of the heights vector is 1, return the answer as heights[0] because there will be only one rectangle width =1 and height = height[0]. 
    • Declare and initialize a variable "maxarea" to INT_MIN. This variable will store the maximum area of the rectangles.
    • Call two other functions “Nsel” and “Nser”. Nsel will basically calculate and give you the values of lIndex, and Nser will give you the value of rIndex. 
    • In the “Nsel” function:
      • Declare a vector lIndex of size n. This vector will store the values of lIndex for each i from 0 to n.
      • Declare a stack s. 
      • Traverse the heights array from i=0 to i<n. 
        • If the stack is empty, this means that the current element is the smallest element till now, thus no element to the left of it is actually smaller than it and they all can be included in the rectangle. Thus, in such case, set lIndex[i] = -1.
        • Else if the stack is not empty, check if the height of the index at the top of the stack is lower than the height of the current index. If yes, lIndex[i] = s.top().
        • Else, keep popping out the top element from the stack until the height of the top element is greater than the height of the current index. If after popping out, the stack becomes empty, this means that the current element is the smallest element till now, thus no element to the left of it is actually smaller than it and they all can be included in the rectangle. Thus, in such case, set lIndex[i] = -1. Otherwise, lIndex[i] = s.top().
        • Push the current index into the stack.
      • Return lIndex.
    • In the “Nser” function, the same above steps are followed except for the case when the stack becomes empty, the value of rIndex[i] is n. And also, we traverse backward in this function.
    • Traverse through each bar in the heights vector. For each i from i=0 to i<n,
      • Calculate the area as heights[i]*(rIndex[i]-lIndex[i]-1).
      • Update the maxarea as max(maxarea,area)
      • Return maxarea.
  • Print answer.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

vector<int> Nsel(vector<int> v){
    int n=v.size();
    vector<int> lIndex(n);  // vector for storing the lIndex values
    stack<int> s; 
    for(int i=0;i<n;i++){
        if(s.empty()) // If the stack is empty, this means that the 
            //current element is the smallest element till now, thus no 
            //element to the left of it actually smaller than it and they 
            //all can be included in the rectangle. Thus, in such case, 
            //set lIndex[i] = -1.
            lIndex[i] = -1;
        else if(!s.empty() && v[s.top()] < v[i])//Else if the stack is not empty, 
            //check if the height of the index at the top of the stack is lower than 
            //the height of the current index. If yes, lIndex[i] = s.top().
            lIndex[i] = s.top();
        else{
            while(!s.empty() && v[s.top()] >= v[i])/*keep popping out the top element 
            from the stack until the height of the top element is greater than the 
            height of the current index.*/
                s.pop();
            if(s.empty())//If after popping out, the stack becomes empty, set lIndex[i] = -1.
                lIndex[i] = -1;
            else //Otherwise, lIndex[i] = s.top()
                lIndex[i] = s.top();
        }
        s.push(i); //Push the current index into the stack
    }
    return lIndex;
}

vector<int> Nser(vector<int> v){
    int n = v.size();
    vector<int> rIndex(n); //vector for storing the rIndex values
    stack<int> s;
    for(int i=n-1;i>=0;i--){
        if(s.empty())// If the stack is empty, this means that from the right, the 
            //current element is the smallest element till now, thus no 
            //element to the right of it actually smaller than it and they 
            //all can be included in the rectangle. Thus, in such case, 
            //set rIndex[i] = n.
            rIndex[i] = n;
        else if(!s.empty() && v[s.top()] < v[i])//Else if the stack is not empty, 
            //check if the height of the index at the top of the stack is lower than 
            //the height of the current index. If yes, rIndex[i] = s.top().
            rIndex[i] = s.top();
        else{
            while(!s.empty() && v[s.top()] >= v[i])/*keep popping out the top element 
            from the stack until the height of the top element is greater than the 
            height of the current index.*/
                s.pop();
            if(s.empty())//If after popping out, the stack becomes empty, set rIndex[i] = n.
                rIndex[i] = n;
            else//Otherwise, rIndex[i] = s.top()
                rIndex[i] = s.top();
        }
        s.push(i);//Push the current index into the stack
    }
    return rIndex;
}

int largestRectangleArea(vector<int>& heights) {
    if(heights.size() ==0)
        return 0;
    if(heights.size() == 1)
        return heights[0];
    //Initialize maxarea to INT_MIN
    int maxarea = INT_MIN;
    // Calculate lIndex and rIndex
    vector<int> lIndex = Nsel(heights); 
    vector<int> rIndex = Nser(heights);
    for(int i=0;i<heights.size();i++){ 
        int area = heights[i]*(rIndex[i]-lIndex[i]-1); //Calculate area for each i
        maxarea = max(maxarea,area); // Keep updating the maxarea
    }
    return maxarea; //Return maxarea
}

int main()
{
    int n;
    cin>>n; //input the number of bars 
    vector<int>heights(n);  // Declare a vector to store the heights of the bars.
    for(int i=0;i<n;i++){
        cin>>heights[i];  // Input the values of the heights
    }
    int ans = largestRectangleArea(heights); // Call the largestRectangleArea function which return the required answer
    cout<<ans<<endl;    //Print the answer.
    return 0;
}

Input

n=6, heights = [2,1,5,6,2,3]

Output

10

Complexities

Time complexity

O(n), where n is the number of bars.

Reason: We’re calculating the lIndex and rIndex values of all the indexes in O(n) time once. Then we’re traversing through the heights vector which takes O(n) time and calculating the area for each i where calculation takes only O(1) time. Thus the time complexity is linear.

Space complexity

O(n), where n is the number of bars.

Reason: We’re storing the lIndex and rIndex values in the arrays lIndex and rIndex and the indexes in the stacks. This takes O(n) space each. Thus the overall space complexity is linear.

 

To know more about conceptual knowledge and the implementation of the code, watch this video tutorial.

Frequently asked questions

  1. What is a histogram?
    A histogram represents a frequency distribution in form of rectangles whose widths (generally 1) represent class intervals and whose areas are proportional to the corresponding frequencies: the height of each is the average frequency density for the interval.
     
  2. What is a monotonic stack?
    A monotonic stack is a special variation of the stack data structure where the elements in the stack are always in a monotonic order, i.e., either increasing or decreasing.
     
  3. Where can I submit my “Largest rectangle in a histogram” code?
    You can submit your code here on Codestudio and get it accepted right away.
     
  4. Are there more Data Structures and Algorithms problems in CodeStudio?
    Yes, CodeStudio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Key Takeaways

In this article, we discussed the problem - Largest rectangle in histogram. This problem was based on monotonic stacks. Similar problems are: trapping rainwatertrapping rainwater IInext greater element, and next smaller element. I suggest you solve these problems.

To practice more such problems, Codestudio is a one-stop destination. You can also Attempt our Online Mock Test Series. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think