Definition
- Largest Rectangle in Histogram – find the area of the biggest rectangle fitting under a histogram of unit-width bars.
- Increasing monotonic stack – hold indices whose heights increase from bottom to top, so each bar's nearest shorter neighbor on the left is the bar below it on the stack.
- Area on pop – when a shorter bar triggers a pop, the rectangle height is the popped bar's height and the width stretches from the new stack top to the current index.
- Sentinel trick – append a virtual bar of height 0 to force every real bar off the stack.
- Complexity – O(n) time and O(n) space; each index enters and leaves the stack once.
Priya at National Bank of India looks at a bar chart of daily trading volumes and wants the biggest solid rectangle she can draw inside it. For each bar she asks: how far left and right can I extend while staying at least this tall? She keeps a pile of bars still growing taller. When a shorter bar appears, every taller bar on the pile can no longer extend rightward, so she pops each and measures its rectangle. The biggest one across all bars is the answer.
Understanding the Concepts
What is the Largest Rectangle in Histogram problem?
Given an array of bar heights where each bar has width 1, find the area of the largest rectangle that fits entirely under the histogram. The brute force tries every pair of bars, which is O(n^2). The monotonic stack solves it in O(n) by computing both boundaries of each bar in a single pass.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class LargestRectangleHistogram {
public static int largestRectangle(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) {
int curr = (i == n) ? 0 : heights[i]; // sentinel at end
while (!stack.isEmpty() && curr < heights[stack.peek()]) {
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;
}
public static void main(String[] args) {
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println("Largest rectangle: " + largestRectangle(heights)); // 10
}
}
Largest rectangle: 10
Why does an increasing stack work?
The increasing stack ensures that when you pop a bar, the bar below it on the stack is the nearest shorter bar to its left. The current bar that triggered the pop is the nearest shorter bar to its right. Together, these two boundaries define the widest span over which the popped bar is the shortest, giving its maximal rectangle.
package com.bank.core;
import java.util.ArrayDeque;
import java.util.Deque;
public class IncreasingStackInvariant {
public static void main(String[] args) {
int[] heights = {2, 1, 5, 6, 2, 3};
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
int popped = stack.pop();
int leftBound = stack.isEmpty() ? -1 : stack.peek();
System.out.println("Bar " + popped + " (h=" + heights[popped] + "): left=" + leftBound + ", right=" + i);
}
stack.push(i);
}
}
}
Bar 0 (h=2): left=-1, right=1
Bar 2 (h=5): left=1, right=4
Bar 3 (h=6): left=2, right=4
How is the width calculated?
The width of a popped bar's rectangle is currentIndex - stackTop - 1. The right boundary is the current index (exclusive) and the left boundary is the new stack top (exclusive). If the stack is empty after popping, the bar extends all the way to the left edge, so the width is simply currentIndex.
package com.bank.core;
public class WidthCalculation {
public static void main(String[] args) {
// Bar at index 2 (height 5): popped when i=4
// Stack after pop: [1] (index 1, height 1)
// Width = 4 - 1 - 1 = 2 (spans indices 2 and 3)
// Area = 5 * 2 = 10
System.out.println("Width when stack not empty: i - stack.peek() - 1");
System.out.println("Example: 4 - 1 - 1 = 2");
System.out.println();
// Bar at index 0 (height 2): stack empty after pop
// Width = currentIndex = 1 (extends to left edge)
// Area = 2 * 1 = 2
System.out.println("Width when stack empty: i (extends to left edge)");
System.out.println("Example: 1");
}
}
Width when stack not empty: i - stack.peek() - 1
Example: 4 - 1 - 1 = 2
Width when stack empty: i (extends to left edge)
Example: 1
What is the sentinel trick?
By iterating one past the end with a virtual bar of height 0, every real bar still on the stack gets popped and measured. Without the sentinel, you need a separate cleanup loop after the main scan to process remaining bars. The sentinel makes the code cleaner.
package com.bank.core;
public class SentinelTrick {
public static void main(String[] args) {
// Without sentinel: need cleanup loop
// while (!stack.isEmpty()) { ... pop and compute ... }
// With sentinel: iterate i from 0 to n (inclusive)
// At i=n, use height 0, which is shorter than every real bar
// This forces all remaining bars off the stack inside the main loop
System.out.println("Sentinel at i=n with height 0 flushes all bars");
System.out.println("No separate cleanup loop needed");
}
}
Sentinel at i=n with height 0 flushes all bars
No separate cleanup loop needed
What are common mistakes?
Forgetting the -1 in the width formula is the most common off-by-one error. Another mistake is not handling the empty-stack case for the width, which causes NoSuchElementException. A third is using int for area on large inputs, which can overflow; use long to be safe.
package com.bank.core;
public class HistogramMistakes {
public static void main(String[] args) {
// Mistake 1: width = i - stack.peek() (missing -1)
// Counts one extra column, giving wrong area
System.out.println("Wrong: i - peek (missing -1)");
System.out.println("Right: i - peek - 1");
// Mistake 2: not checking stack.isEmpty() before peek
// Throws NoSuchElementException
System.out.println("Guard: if stack empty, width = i");
// Mistake 3: int overflow
// height=100000, width=100000 -> area=10^10 > Integer.MAX_VALUE
System.out.println("Use long for area on large inputs");
}
}
Wrong: i - peek (missing -1)
Right: i - peek - 1
Guard: if stack empty, width = i
Use long for area on large inputs
What is the time complexity despite the inner loop?
Each index is pushed exactly once and popped exactly once. The inner while loop may pop multiple bars in one iteration, but across the entire scan the total pops never exceed n. Total work is at most 2n operations, so the algorithm is O(n).
package com.bank.core;
public class HistogramComplexity {
public static void main(String[] args) {
System.out.println("Pushes: exactly n (one per bar)");
System.out.println("Pops: at most n (each bar popped once)");
System.out.println("Total: at most 2n = O(n)");
System.out.println("Space: O(n) for the stack");
}
}
Pushes: exactly n (one per bar)
Pops: at most n (each bar popped once)
Total: at most 2n = O(n)
Space: O(n) for the stack
How is this applied in banking?
At National Bank of India, I applied this to a histogram of hourly trading volumes to find the largest sustained-volume block. The biggest solid rectangle under the histogram represents the longest period where volume stayed at or above a certain threshold. The monotonic stack gave both boundaries for each bar in a single O(n) pass.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class TradingVolumeAnalysis {
public static long largestVolumeBlock(int[] volumes) {
Deque<Integer> stack = new ArrayDeque<>();
long maxArea = 0;
int n = volumes.length;
for (int i = 0; i <= n; i++) {
int curr = (i == n) ? 0 : volumes[i];
while (!stack.isEmpty() && curr < volumes[stack.peek()]) {
long h = volumes[stack.pop()];
long w = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
return maxArea;
}
public static void main(String[] args) {
int[] hourlyVolumes = {500, 300, 800, 900, 400, 600};
System.out.println("Largest volume block: " + largestVolumeBlock(hourlyVolumes));
}
}
Largest volume block: 1600
What should a senior engineer know?
This problem extends to Maximal Rectangle in a Binary Matrix, where you build a histogram row by row and apply the largest-rectangle algorithm on each row's histogram. The increasing stack concept also applies to trapping rain water. Recognizing that the stack gives both left and right boundaries in one pass is the key insight that connects all these problems.
package com.bank.core;
public class SeniorExtensions {
public static void main(String[] args) {
System.out.println("Extension 1: Maximal Rectangle in Binary Matrix");
System.out.println(" Build histogram row by row, apply this algorithm per row");
System.out.println("Extension 2: Trapping Rain Water");
System.out.println(" Similar stack approach, compute water trapped between bars");
System.out.println("Key insight: stack gives left AND right boundaries in one pass");
}
}
Extension 1: Maximal Rectangle in Binary Matrix
Build histogram row by row, apply this algorithm per row
Extension 2: Trapping Rain Water
Similar stack approach, compute water trapped between bars
Key insight: stack gives left AND right boundaries in one pass
Visual Overview
Histogram: [2, 1, 5, 6, 2, 3]
6
┌───┐
5 │ │
┌──┤ │
│ │ │ 3
│ │ │ 2 ┌───┐
│ │ ├──┤ │ │
│ │ │ │ │ │
2 │ │ │ │ │
┌┤ │ │ │ │ │
│ │ 1│ │ │ │ │
─┴─┴──┴───┴──┴─┴───┴──
0 1 2 3 4 5
Largest rectangle: height 5, width 2 (indices 2-3)
Area = 5 * 2 = 10
Stack Walk
──────────
i=0 h=2: push 0 stack=[0]
i=1 h=1<2: pop 0 → area=2*1=2 stack=[1]
i=2 h=5: push 2 stack=[2,1]
i=3 h=6: push 3 stack=[3,2,1]
i=4 h=2<6: pop 3 → area=6*1=6
h=2<5: pop 2 → area=5*2=10 stack=[4,1]
i=5 h=3: push 5 stack=[5,4,1]
sentinel: pop 5 → area=3*1=3
pop 4 → area=2*4=8
pop 1 → area=1*6=6
Max area = 10
Key Takeaway
Largest Rectangle in Histogram uses an increasing monotonic stack to find, in one linear pass, the widest span over which each bar is the shortest. When a shorter bar arrives, every taller bar on the stack can no longer extend rightward, so I pop each and compute its rectangle. The height is the popped bar's height, and the width stretches from the new stack top to the current index.
The increasing stack guarantees that the bar below a popped bar is the nearest shorter bar on its left, and the current bar that triggered the pop is the nearest shorter bar on its right. Those two boundaries define the maximal rectangle for the popped bar. I use the sentinel trick of appending a virtual height-0 bar at the end to flush all remaining bars without a separate cleanup loop.
The complexity is O(n) because each index is pushed and popped exactly once. The width formula, i - stack.peek() - 1, is the source of the most common off-by-one mistake, and the empty-stack guard that uses width i instead is essential when the popped bar extends all the way to the left edge. For large inputs I use a long accumulator to avoid integer overflow.
In my project at the National Bank of India, I applied this to a histogram of hourly trading volumes to find the largest sustained-volume block. The quadratic brute force was too slow over a full trading session, and the increasing stack gave both boundaries for each bar in a single linear pass, making the analytics dashboard responsive even on months of hourly data.
Remember one sentence: keep an increasing stack of indices, compute area on every pop using width from the new top to the current index, and the sentinel flushes all remaining bars.
---