Header Ads Widget

Trending

6/recent/ticker-posts

Largest Rectangle in a Histogram

 Problem-: Largest Rectangle in a Histogram

We have to find the largest area of a rectangle in a Histogram. we have given an Array of Integers representing a Histogram where the width of each bar is 1 Unit and height is the value of each index in the Histogram array. The largest rectangle in Histogram is that whose area is highest among all rectangles so formed.

Let us Understand how we can calculate largest area of rectangle in Histogram using Example.

Example 1 :

Your input
[2,12,3,10,5,8,1,4]
Output
15

Have a Look at Visualization Histogram 


Largest Rectangle in a Histogram

The basic Logic behind solving this problem is that we will get the largest triangle until we get an element lower than that element.

  Also Read  -   [ Tower of Hanoi Problem ]

Brute force solution is the easiest way to understand this problem.

 Brute force approach for Largest Triangle in Histogram.


class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length==1return heights[0];
       
        int area=0;
        for(int i=0;i<heights.length;i++)
        {
             int min=Integer.MAX_VALUE;
            for(int j=i;j<heights.length;j++)
            {
                min=Math.min(min,heights[j]);
                area=Math.max(area,(j-i+1)*min);
               
            }   
        }
        
        return area;   
    }
}


After Going through the Brute force approach, you would understand the question and an approach to solve it.
As this Above solution will give TLE
     Now let us Modify it to an efficient approach.

Solution of Largest Rectangle in a Histogram in Java

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length==1return heights[0];
        Stack<Integer> st = new Stack();
        st.add(0);
        int i=0;
        int area=0;
        while(i<heights.length)
        {
            
         
                while(!st.isEmpty() && heights[i]<heights[st.peek()])
                {
                    int t=st.peek();
                    int h= heights[t];
                    st.pop();
                    if(st.isEmpty())
                    {
                        area=Math.max(area,h*i);
                    }
                    else
                    {
                        int len=i-st.peek()-1;
                        area=Math.max(area,h*len);
                    }
                    
                    
                }
          
            st.add(i);
            i++;
            
        }
        
        while(!st.isEmpty())
                {
                    int t=st.peek();
                    int h= heights[t];
                    st.pop();
                    if(st.isEmpty())
                    {
                        area=Math.max(area,h*i);
                    }
                    else
                    {
                        int len=i-st.peek()-1;
                        area=Math.max(area,h*len);
                    }
                    
                    
                }
        
        
        return area;
        
    }
}

Solution of Largest Rectangle in a Histogram in C++

int largestRectangleHistogram(vector<int>& height
{
    int n = height.size();
    int  max=0;
    vector<intleft(n), right(n);
    stack<int> st;
    for(int i=0; i<n; i++)
    {
        if(st.empty())
        {
            left[i] = 0st.push(i);
        }
        
        while(!st.empty() and height[st.top()] >= height[i])
            st.pop();
        left[i] = st.empty()?0:st.top()+1
        st.push(i);
    }
    
    while(!st.empty())
        st.pop();
    
    for(int i=n-1; i>=0; i--)
    {
        if(st.empty())
        {
            right[i] = n-1st.push(i);
        }
        
        while(!st.empty() and height[st.top()] >= height[i])
            st.pop();
        right[i] = st.empty()?n-1:st.top()-1;   
        st.push(i);
    }
    
    for(int i=0; i<n; i++)
    {
        max = max(max, height[i]*(right[i]-left[i]+1));
    }
    return max;
    
}
};


The time complexity of the Largest Rectangle in the Histogram is O(n) if we use our stack approach.
Space Complexity of Largest Rectangle in Histogram is O(n).

 The above solution is given by using Stack but You can use "Divide and conquer" algorithm to solve it more efficiently.

Solve this Problem at Leetcode

Leetcode problem Number 84 - Largest Rectangle in a Histogram