NUHMAN.com

Largest Rectangle in a Histogram (Java Stack Solution)

🧩 Problem Statement

Given an integer array heights, where each element represents the height of a bar in a histogram and each bar has a width of 1, return the area of the largest rectangle that can be formed within the bounds of the histogram.

⚙️ Intuition & Strategy

To efficiently solve this problem in O(n) time, we use a monotonic stack to keep track of the indices of increasing bar heights. When we encounter a bar shorter than the bar on top of the stack, we calculate the area for the bar popped off as the shortest bar.

🔢 Step-by-Step Approach

1. Use a Stack to store indices of bars in increasing height order.
2. Iterate through all bars, including a dummy bar of height 0 at the end:

• If the current bar is taller, push its index to the stack.
• If the current bar is shorter, pop from the stack and calculate the area using the popped height as the smallest height.

1. Track the max area during the process.

✅ Java Implementation

java

import java.util.Stack;

public class LargestRectangleHistogram {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            int currentHeight = (i == n) ? 0 : heights[i];

            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }

            stack.push(i);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        int result = largestRectangleArea(heights);
        System.out.println("The largest rectangle area is: " + result);
    }
}

🔍 Example Walkthrough

Input:

heights = {2, 1, 5, 6, 2, 3}

Visual:

markdown

|       |  
|   |   |  
| | | | |  
-----------
 2 1 5 6 2 3

Output:

csharp

The largest rectangle area is: 10

Explanation: The largest rectangle is formed by bars of height 5 and 6 (width = 2), giving area = 5 * 2 = 10.

📌 Key Concepts

• Time Complexity: O(n) — Each bar is pushed and popped at most once.
• Space Complexity: O(n) — Stack stores bar indices.
• Edge Case Handling: Append a dummy height of 0 to force processing of all bars.

🧠 Use Cases

• Histogram data analysis
• Dynamic area calculations
• Problems like:
• Maximal Rectangle in Binary Matrix
• Skyline silhouette generation
• Stock span problems