Largest Rectangle in Histogram in Java: Explanation & Practice

Problem summary

Given array of bar heights, find the largest rectangular area in the histogram. Classic monotonic stack problem.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        
        // For each bar, find how far it can extend left and right
        // Use stack to find previous and next smaller elements
        // Print: Max area: 10
    }
}

Expected output and test cases

• [2,1,5,6,2,3] → 5*2

  Max area: 10

• [2,4] → 2*2

  Max area: 4

• [2,1,2] → 1*3 or 2*1

  Max area: 3

Hints

1. For each bar, area = height × width
2. Width = distance between previous smaller and next smaller bar
3. Use monotonic increasing stack
4. When we pop a bar, current position is its right boundary

Related Data Structures & Algorithms exercises

• Practice Next Greater Element in Java
• Practice Daily Temperatures in Java
• Practice Min Stack in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler