#84 Largest Rectangle in Histogram
frequently reported atFlipkartAmazonGoogleMicrosoftBloombergMeta
the problem
In plain words
Bars of width 1 have the given heights. Return the area of the largest rectangle that fits entirely inside the histogram.
in heights = [2,1,5,6,2,3]
out 10
Bars 5 and 6 form a 5 × 2 rectangle.
in heights = [2,4]
out 4
- 1 ≤ heights.length ≤ 10⁵
- 0 ≤ heights[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMonotonic stack
The best rectangle has some bar as its shortest bar. That bar's rectangle stretches left and right until the nearest shorter bar on each side — and an increasing stack finds both neighbours.
solutions
From brute force to optimal
For each start i, extend j to the right, keeping the minimum height so far.
- For each i: min = ∞.
- For each j ≥ i: min = min(min, h[j]); best = max(best, min × (j − i + 1)).
All n(n+1)/2 ranges, O(1) each.
A few counters.
class Solution { public int largestRectangleArea(int[] heights) { int best = 0; for (int i = 0; i < heights.length; i++) { int minHeight = Integer.MAX_VALUE; for (int j = i; j < heights.length; j++) { // every range [i, j] minHeight = Math.min(minHeight, heights[j]); best = Math.max(best, minHeight * (j - i + 1)); } } return best; }}Precompute, for each bar, the index of the nearest shorter bar on the left and on the right.
- Left pass with an increasing stack → left[i] (or −1).
- Right pass → right[i] (or n).
- best = max over i of h[i] × (right[i] − left[i] − 1).
Two monotonic-stack passes plus one loop.
Two arrays and a stack.
class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; int[] left = new int[n]; // index of nearest smaller bar on the left, or -1 int[] right = new int[n]; // index of nearest smaller bar on the right, or n Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop(); left[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } stack.clear(); for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop(); right[i] = stack.isEmpty() ? n : stack.peek(); stack.push(i); } int best = 0; for (int i = 0; i < n; i++) { best = Math.max(best, heights[i] * (right[i] - left[i] - 1)); // bar i is the shortest } return best; }}When bar i is shorter than the top, the top bar can't extend past i. Its left wall is the bar below it on the stack. Measure it and pop.
- Loop i from 0 to n, treating h[n] = 0 so everything gets flushed.
- While the top bar is ≥ h: pop it; width = i − (new top, or −1) − 1; best = max(best, height × width).
- Push i.
Each bar is pushed once and popped once.
An increasing input keeps every bar on the stack.
class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length, best = 0; Deque<Integer> stack = new ArrayDeque<>(); // indices; heights increase bottom -> top for (int i = 0; i <= n; i++) { int h = (i == n) ? 0 : heights[i]; // a final 0 flushes every bar out while (!stack.isEmpty() && heights[stack.peek()] >= h) { int height = heights[stack.pop()]; int left = stack.isEmpty() ? -1 : stack.peek(); int width = i - left - 1; best = Math.max(best, height * width); } stack.push(i); } return best; }}Dry run
in the room
How to say it in the interview
talk track
- Start with the reframing: "for each bar, the widest rectangle where it is the shortest bar."
- That needs the nearest shorter bar on both sides — classic monotonic stack.
- Present the two-pass version first if nervous; it's easier to explain. Then fold it into one pass.
- Mention the height-0 sentinel that flushes the stack at the end.
traps
- Width off by one: it's
i − left − 1, whereleftis the index below the popped bar on the stack (or −1). - Forgetting to flush the stack at the end — an increasing histogram like [1,2,3] would return 0.
what they ask next
Follow-ups
Maximal Rectangle (LC 85) in a 0/1 matrix?
Treat each row as the floor of a histogram (heights = consecutive 1s above). Run this algorithm per row: O(rows × cols).
before you submit
Edge cases to test
- A rising histogram never pops until the end — the height-0 sentinel at i = n flushes it.
- Equal heights: [3, 3, 3] → 9.
- A zero-height bar: nothing can stretch across it.
- The biggest area, 10⁵ bars × 10⁴ height = 10⁹, still fits in an int.
practise next
Similar problems
- #739Daily TemperaturesMediumin Stacks
- #42Trapping Rain WaterHardin Two Pointers
- #11Container With Most WaterMediumin Two Pointers