Largest Rectangle in Histogram

LeetCode 84 | Difficulty: Hard

Hard

Problem Description

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 <= 10^5`

- `0 <= heights[i] <= 10^4`

Topics: Array, Stack, Monotonic Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

---

Solutions

Solution 1: C# (Best: 100 ms)

Metric	Value
Runtime	100 ms
Memory	26.7 MB
Date	2020-03-07

Solution

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int len = heights.Length;
    Stack<int> s = new Stack<int>();
    int maxArea = 0;
    for (int i = 0; i <= len; i++)
    {
        int h = (i == len ? 0 : heights[i]);
        if(s.Count == 0 || h >= heights[s.Peek()]){
            s.Push(i);          
        }
        else
        {
            int tp = s.Pop();
            maxArea = Math.Max(maxArea, heights[tp] * (s.Count==0 ? i : i-1-s.Peek()));
            i--;
        }
    }
    return maxArea;
    }
}

📜 1 more C# submission(s)

Submission (2022-01-20) — 383 ms, 48.3 MB

public class Solution {
    public int LargestRectangleArea(int[] heights) {
    int len = heights.Length;
    Stack<int> s = new Stack<int>();
    s.Push(-1);
    int maxArea = 0;
    for(int i=0;i<len;i++)
    {
        if(s.Peek() == -1 || heights[i]>=heights[s.Peek()])
        {
            s.Push(i);
        }
        else
        {
            while(s.Peek() != -1 && heights[s.Peek()]>heights[i])
            {
                var top = s.Pop();
                maxArea = Math.Max(maxArea, heights[top] * (i-s.Peek()-1));
            }
            s.Push(i);
        }
    }
    while(s.Peek() != -1)
    {
        var top = s.Pop();
        maxArea = Math.Max(maxArea, heights[top]*(len-s.Peek()-1));
    }
    return maxArea;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?