Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.


Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].


The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Solution

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        
        int i = 0;
        
        for(i=0;i<heights.Length;i++)
        {
            int currentElement = heights[i];
            
            if(stack.Count == 0)
                stack.Push(i);
            
            else
            {
                int topElementInStack = heights[stack.Peek()];
                
                if(topElementInStack <= currentElement)  
                {
                    stack.Push(i);
                }
                else
                {
                    //Pop stack until topElementInStack <= currentElement
                    while(stack.Count > 0 && heights[stack.Peek()] > currentElement)
                    {
                        int poppedElement = heights[stack.Pop()];
                        
                        //Find Area
                        if(stack.Count == 0)
                        {
                            int area = poppedElement * i;
                            maxArea = Math.Max(area,maxArea);
                        }
                        else
                        {
                            int area = poppedElement * (i - stack.Peek() - 1);    
                            maxArea = Math.Max(area,maxArea);
                        }
                    }
                    
                    stack.Push(i);
                }
            }
        }
        
        while(stack.Count > 0)
        {
            int poppedElement = heights[stack.Pop()];
            
            //Find Area
            if(stack.Count == 0)
            {
                int area = poppedElement * i;
                maxArea = Math.Max(area,maxArea);
                break;
            }
            else
            {
                int area = poppedElement * (i - stack.Peek() - 1);
                maxArea = Math.Max(area,maxArea);
            }
        }
        return maxArea;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s