Largest Rectangle In Histogram Problem Solution

Largest Rectangle In Histogram: Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Largest Rectangle In Histogram Problem Solution

Problem Solution In Python

class Solution:
    def largestRectangleArea(self, arr: List[int]) -> int:
        stack,pos,maxA=[],0,0
        n=len(arr)
        for i in range(n):
            
            while(stack and arr[stack[-1]]>arr[i]):
                pos= stack.pop()
                if stack:
                    area=arr[pos]*(i-stack[-1]-1)
                    maxA=max(maxA,area)
                else:
                    area=arr[pos]*(i-0)
                    maxA=max(maxA,area)
                    
                    
            stack.append(i)
          
        while stack:
                
                pos= stack.pop()
                if stack:
                    area=arr[pos]*(n-stack[-1]-1)
                    maxA=max(maxA,area)
                else:
                    area=arr[pos]*(n-0)
                    maxA=max(maxA,area)
                
        
        return maxA

Problem Solution In Java

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack < Integer > stack = new Stack < > ();
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        Arrays.fill(right,heights.length);
        Arrays.fill(left,-1);
        for(int i = 0;i<heights.length;i++){
            while(!stack.empty()&&heights[stack.peek()]>heights[i]){
                right[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        stack = new Stack<>();
        for(int i = heights.length-1;i>=0;i--){
            while(!stack.empty()&&heights[stack.peek()]>heights[i]){
                left[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        
        int maxArea = 0;
        for (int i = 0; i < heights.length; ++i) {
            maxArea = Math.max(maxArea,(right[i]-left[i]-1)*heights[i]);
        }
        
        return maxArea;
    }
}

Problem Solution In C++

int largestRectangleArea(vector<int>& arr) {
        int n=arr.size();
        if(n==0) return 0;
        stack<int> s;
        int i=0,area=INT_MIN;
        while(i<n)
        {
            if(s.empty()||arr[s.top()]<=arr[i])
            {
                s.push(i);i++;
            }
            else
            {
                int num=s.top();s.pop();
                int l=s.empty()?-1:s.top();
                area=max(area,arr[num]*(i-l-1));
            }
        }
        while(!s.empty())
        {
            int num=s.top();s.pop();
                int l=s.empty()?-1:s.top();
                area=max(area,arr[num]*(i-l-1));
        }
        return area;
    }

Problem Solution In C

struct tagStackObj{
    int height;
    int width;
};

int largestRectangleArea(int* heights, int heightsSize){
    int maxSize = 0;
    int squareSize = 0;
    int i;
    int *p = heights;
    int index = 0;
    int stride = 0;
    struct tagStackObj *pStack = NULL;
    
    if (0 == heightsSize)
        return 0;
    
    pStack = malloc(heightsSize * sizeof(struct tagStackObj));
    pStack[index].width = 1;
    pStack[index].height = heights[0];
    
    for (i = 1; i < heightsSize; i++){
        if (p[i] >= pStack[index].height){
            index++;
            pStack[index].height = p[i];
            pStack[index].width = 1;
        }
        else{
            stride = 0;
            while ((index >= 0) && (pStack[index].height > p[i])){
                stride += pStack[index].width;
                squareSize = stride * pStack[index].height;
                maxSize = squareSize > maxSize ? squareSize : maxSize;
                index--;
            }
            
            pStack[++index].height = p[i];
            pStack[index].width = stride + 1;
        }
    }
    
    stride = 0;
    while ((index >= 0) && (pStack[index].height > -1)){
        stride += pStack[index].width;
        squareSize = stride * pStack[index].height;
        maxSize = squareSize > maxSize ? squareSize : maxSize;
        index--;
    }
    
    return maxSize;
}

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment