LeetCode 84. Largest Rectangle in Histogram

Description

https://leetcode.com/problems/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.

Example 1:

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.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

Video Tutorial

Java Solution

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        
        for (int i = 0; i < heights.length; i++) {
            int currentBarHeight = heights[i];
            
            while (stack.peek() != -1 && currentBarHeight <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                
                int area = height * width;
                maxArea = Math.max(area, maxArea);
            }          
            
            stack.push(i);
        }
        
        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            
            int area = height * width;
            maxArea = Math.max(area, maxArea);
        }
        
        return maxArea;
        
        // Time complexity : O(n). n numbers are pushed and popped.
        // Space complexity : O(n). Stack is used.
    }
}

Python Solution

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if not heights:
            return 0
        
        max_area = 0
        
        stack = []
        stack.append(-1)
        
        
        for i in range(len(heights)):
            current_height = heights[i]
            
            while stack[-1] != -1 and current_height < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                
                area = height * width
                
                max_area = max(area, max_area)
                
                
            stack.append(i)
            
        while stack[-1] != -1:
            height = heights[stack.pop()];
            width = len(heights) - stack[-1] - 1
            
            area = height * width
            max_area = max(area, max_area)
        
        return max_area

• Time Complexity: O(N)
• Space Complexity: O(N)