7. Largest Rectangle in Histogram

Description

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

Approach

• The thing is we store index in our stack and not the element itself when we encounter a smaller height we just need to calculate area up until now
• we use that i == n condition because there is no index at n so that is set to zero but we can have elements in the stack still so this is more of a forcing condition for next loop
• for height we pop then we peek that is because we are trying to pick the last two tallest from stack and do the calculation
• Complexities are all n

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<>();
        int maxArea = 0, n = heights.length;
 
        for (int i = 0; i <=n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!st.isEmpty() && h < heights[st.peek()]) {
                int height = heights[st.pop()];
                int width = st.isEmpty() ? i : i - st.peek() - 1;
                maxArea = Math.max(maxArea, height*width);
            }
            st.push(i);
        }
 
        return maxArea;
    }
}

Approach 1: Brute Force ($O(N^2)$)

Intuition

For every bar $i$, consider it as the shortest bar (bottleneck) of a potential rectangle. Expand to the right to find the minimum height across every sub-range $[i,j]$, calculate minHeight * width, and track the global maximum.

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
 
        for (int i = 0; i < n; i++) {
            int minHeight = heights[i];
 
            for (int j = i; j < n; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                int width = j - i + 1;
                maxArea = Math.max(maxArea, minHeight * width);
            }
        }
 
        return maxArea;
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — Evaluates all possible sub-ranges using nested loops (results in Time Limit Exceeded).
• Space Complexity: $O(1)$ — Uses standard variables.

---

Most Optimized Solution: Monotonic Stack ($O(N)$)

Intuition

Instead of testing all sub-ranges, use a Monotonic Increasing Stack storing indices of bars:

1. As you iterate through heights, if the current bar currentHeight is shorter than the height at stack.peek(), the bar at the stack top can no longer extend any further to the right.
2. Pop that bar’s index and take its height as $H$.
3. The right boundary is the current index $i$, and the left boundary is the new stack top index (stack.peek()). The width is $i-\text{stack.peek()}-1$ (or simply $i$ if the stack is empty).
4. Update maxArea with $H\times \text{width}$.
5. Process an extra virtual iteration at index $N$ with height 0 to force-pop and calculate the area for all remaining bars in the stack.

import java.util.Stack;
 
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
 
        for (int i = 0; i <= n; i++) {
            // Virtual height 0 at the end to flush out all remaining bars in stack
            int currentHeight = (i == n) ? 0 : heights[i];
 
            while (!stack.isEmpty() && heights[stack.peek()] > currentHeight) {
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
 
            stack.push(i);
        }
 
        return maxArea;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every index is pushed and popped from the stack at most once across a single pass.
• Space Complexity: $O(N)$ — Stores up to $N$ indices in the stack in the worst-case scenario.

---

Easy Memory Rule

“Maintain an increasing height stack. When a shorter bar arrives, pop taller bars using current index $i$ as the right boundary and the new stack top as the left boundary.”

What is a Monotonic Stack?

A Monotonic Stack is a standard stack data structure that maintains its elements in a fixed sorted order (either entirely increasing or entirely decreasing) from bottom to top.

• Monotonic Increasing Stack: Elements strictly increase from bottom to top (smallest element at the bottom, largest at the top).
• Monotonic Decreasing Stack: Elements strictly decrease from bottom to top (largest element at the bottom, smallest at the top).

---

Why Use It in “Largest Rectangle in Histogram”?

1. The Core Problem Logic

To find the maximum rectangular area formed by any bar $i$ acting as the height $H$:

• You need to find the first shorter bar to the left (left boundary).
• You need to find the first shorter bar to the right (right boundary).
• The width is then calculated as: $\text{width}=\text{right\_index}-\text{left\_index}-1$.

2. The Brute Force Bottleneck

Searching left and right individually for each bar takes $O(N)$ time per bar, resulting in an inefficient $O(N^2)$ overall time complexity.

3. How the Monotonic Increasing Stack Achieves $O(N)$

• Detecting the Right Boundary: As we iterate through the array, encountering a bar shorter than heights[stack.peek()] signals that the top element has hit its first smaller element on the right.
• Detecting the Left Boundary: After popping that taller element, the new top of the stack (stack.peek()) represents its first smaller element on the left.
• $O(1)$ Computation: Both boundaries are discovered simultaneously during stack operations, allowing us to compute the maximum area for each bar in linear time.

---

Key Takeaways for Documentation

• Time Complexity: $O(N)$ — Every index is pushed and popped from the stack at most once.
• Space Complexity: $O(N)$ — In the worst case (a strictly increasing array), all indices are stored in the stack.
• General Pattern Recognition: Use a Monotonic Stack whenever a problem requires finding the Next/Previous Greater or Smaller Element across an array.