Largest Rectangle in Histogram Using Stack in DSA C# - Deep Dive

Overview - Largest Rectangle in Histogram Using Stack

What is it?

Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed within the histogram boundaries. A rectangle must be entirely contained within consecutive bars and cannot exceed the height of any bar it spans. The stack-based solution finds the optimal rectangle in O(n) time by tracking bars whose extent hasn't yet been determined.

Why it matters

This problem demonstrates a powerful stack pattern: using a monotonic stack to efficiently compute the 'nearest smaller element' relationship. This pattern appears in stock span, next greater element, trapping rain water, and maximal rectangle in binary matrix — all common interview problems. Mastering it unlocks an entire class of O(n) solutions to problems that naively require O(n²).

Where it fits

You need comfort with stacks, array indexing, and area calculation before tackling this. After mastering it, Trapping Rain Water, Maximal Rectangle in Binary Matrix, and Next Greater Element follow as direct applications of the same monotonic stack pattern.

Mental Model

Core Idea

A bar can extend leftward as long as all bars to its left are at least as tall. The stack tracks bars in increasing height order — when a shorter bar appears, it forces all taller bars behind it to compute their maximum width.

Think of it like...

Imagine stacking increasingly tall books on a shelf left to right. When you place a shorter book, every taller book behind it has just found its rightmost boundary. You calculate how far left each tall book could have extended and record the largest bookshelf rectangle before removing it.

Heights: [2, 1, 5, 6, 2, 3]

Stack evolution (storing indices):
After i=0 (h=2): stack=[0]
After i=1 (h=1): h[1]<h[0] → pop 0, area=2×1=2. Push 1. stack=[1]
After i=2 (h=5): stack=[1,2]
After i=3 (h=6): stack=[1,2,3]
After i=4 (h=2): h[4]<h[3] → pop 3, area=6×1=6
                  h[4]<h[2] → pop 2, area=5×(4-1-1)=10 ← MAX
                  h[4]≥h[1]. Push 4. stack=[1,4]
After i=5 (h=3): stack=[1,4,5]
Drain stack: pop 5, area=3×(6-4-1)=3
             pop 4, area=2×(6-1-1)=8
             pop 1, area=1×6=6
Answer: 10

Build-Up - 6 Steps

1

Foundation

Why Brute Force is O(n²)

Concept: For every pair of bars (i, j), compute the rectangle height as min(heights[i..j]) × (j-i+1).

The brute force approach tries every possible left and right boundary for a rectangle. For each pair (i, j), the rectangle height is limited by the shortest bar in that range. Computing this minimum for all pairs takes O(n²) time. With n up to 100,000 bars, this is too slow. We need to avoid re-scanning for minimums — the stack does this in one pass.

Result

Understanding brute force confirms that finding the minimum bar height for each span is the bottleneck to eliminate.

The stack replaces the inner minimum search by maintaining the invariant that popped bars always know their left and right boundaries at pop time.

2

Foundation

Monotonic Increasing Stack — The Core Invariant

Concept: The stack always holds bar indices in increasing height order from bottom to top.

We push bar indices as long as the current bar is taller than the stack top. When we encounter a bar shorter than the top, the top bar has found its right boundary (current index) and its left boundary (new stack top + 1 after popping). At this moment we compute its maximum rectangle area. This is the key: a bar stays in the stack only while it might still extend rightward.

Result

Each bar is pushed once and popped once — O(n) total operations.

A bar is popped exactly when we find the first bar to its right that is shorter — this is precisely the right boundary of its maximum rectangle.

3

Intermediate

Area Calculation on Pop

🤔Before reading on: when we pop index 'top' from the stack at position 'i', what are the left and right boundaries of the rectangle with height heights[top]? Commit to your answer.

Concept: Width = right_boundary - left_boundary - 1, where right = i and left = new stack top (or -1 if empty).

When we pop index 'top' at position 'i': right boundary = i (exclusive, the bar that triggered the pop). Left boundary = stack.Count > 0 ? stack.Peek() : -1 (the bar below in the stack, which is shorter, so our rectangle can't extend past it). Width = i - left - 1. Area = heights[top] × width. Track the maximum area seen.

Result

Correct area formula derived from stack state at pop time.

The left boundary is always the current stack top AFTER popping — because that bar is shorter and blocks leftward extension. If the stack is empty, the bar extends to index -1 (left edge of the histogram).

4

Intermediate

Draining the Stack at the End

🤔Before reading on: after processing all bars, what happens to bars still in the stack that never found a shorter bar to their right? Commit to your answer.

Concept: Remaining bars in the stack extend to the right edge of the histogram (index n).

After the main loop, some bars remain in the stack — they never encountered a shorter bar to their right. Their right boundary is n (one past the last index). Pop each remaining bar with right = n. Width = n - (new stack top after pop) - 1. Compute area and update maximum. In C#: while (stack.Count > 0) { int top = stack.Pop(); int left = stack.Count > 0 ? stack.Peek() : -1; area = heights[top] * (n - left - 1); }

Result

All bars are processed and no valid rectangle is missed.

Forgetting to drain the stack is the most common implementation bug — it misses all bars that are bounded only on the left.

5

Advanced

Sentinel Value Trick — Avoid Separate Drain Loop

🤔Before reading on: can you avoid the separate stack drain loop by appending a 0-height bar at the end? Commit yes or no.

Concept: Append a virtual bar of height 0 at index n to force all remaining bars to pop during the main loop.

Extend heights by one element: heights = heights.Append(0).ToArray() or use a manual check for index == n with height = 0. This forces every bar still in the stack to be popped during the main loop when the virtual 0-height bar is processed. The drain loop is eliminated — the main loop handles everything. The left boundary for the last bar in the stack is still -1 (stack empty) as before.

Result

Simpler, more elegant implementation with a single loop.

Adding a sentinel 0 at the end is a common interview trick that simplifies the code without changing correctness. Recognize both implementations.

6

Expert

Stack Stores Indices, Not Heights

🤔Before reading on: why does the stack store bar INDICES rather than bar HEIGHTS directly? Commit to your answer.

Concept: Storing indices enables width calculation — you need to know the position, not just the height, to compute left boundary.

When popping bar 'top', the left boundary is stack.Peek() (the index below in the stack, not just its height). If we stored only heights, we'd have no way to compute the left boundary position. Storing indices gives us both: heights[top] for the height and the index itself for position. This is a general principle: monotonic stacks store indices when position matters.

Result

Correct width computation using indices of neighboring bars in the stack.

Always store indices in monotonic stacks when you need to compute spans, ranges, or distances. The value can always be retrieved as heights[index] — the position cannot be recovered from the value alone.

Under the Hood

The stack maintains the invariant that indices are in strictly increasing height order. When bar i is shorter than stack.Peek(), it triggers pops until the invariant is restored. Each pop computes the maximum rectangle for the popped bar using the current index as right boundary and the new stack top as left boundary. Total work: O(n) pushes + O(n) pops = O(n).

Why designed this way?

The naive O(n²) approach re-scans leftward from each bar to find the left boundary. The stack eliminates this re-scan by maintaining the left boundary implicitly — it's always the element below the popped bar in the stack. This is the same insight behind all monotonic stack algorithms: precompute nearest-smaller relationships in O(n) by processing left-to-right.

Heights: [2, 1, 5, 6, 2, 3], n=6

i=0: push 0. Stack=[0]
i=1: h[1]=1 < h[0]=2. Pop 0: left=-1, area=2×(1-(-1)-1)=2. Push 1. Stack=[1]
i=2: push 2. Stack=[1,2]
i=3: push 3. Stack=[1,2,3]
i=4: h[4]=2<h[3]=6. Pop 3: left=2, area=6×(4-2-1)=6.
     h[4]=2<h[2]=5. Pop 2: left=1, area=5×(4-1-1)=10. ★MAX
     h[4]≥h[1]=1. Push 4. Stack=[1,4]
i=5: push 5. Stack=[1,4,5]
Drain: Pop 5: left=4, area=3×(6-4-1)=3.
       Pop 4: left=1, area=2×(6-1-1)=8.
       Pop 1: left=-1, area=1×(6-(-1)-1)=6.
Result: 10

Myth Busters - 4 Common Misconceptions

Quick: is the left boundary of a popped bar the bar immediately to its left in the array? Commit yes or no.

Common Belief: The left boundary is always the bar at index top-1 in the original array.

Reality: The left boundary is the bar at the index currently at the top of the stack AFTER popping — which may be several positions to the left if intervening taller bars were already popped.

Why it matters: Using top-1 as the left boundary gives wrong widths. The stack top after popping is the correct left boundary because it's the nearest bar that is shorter than the popped bar.

Quick: if the stack is empty when we pop a bar, what is the left boundary? Commit to your answer.

Common Belief: If the stack is empty, the left boundary is 0.

Reality: If the stack is empty after popping, the left boundary is -1, meaning the rectangle extends all the way to the left edge of the histogram. Width = i - (-1) - 1 = i.

Why it matters: Using 0 as left boundary when stack is empty makes the width one shorter than the correct value, producing the wrong area for bars that span the entire left portion of the histogram.

Quick: should you pop when the current height equals the stack top height? Commit yes or no.

Common Belief: Only pop when the current height is strictly less than the stack top height.

Reality: Either strict or non-strict comparison works, but they affect which duplicate-height bar computes the area. Strict less-than (<) is most common and correct — equal heights are pushed onto the stack and computed at the next strictly shorter bar.

Why it matters: Both approaches give the correct maximum area. Strict less-than is simpler and avoids potential issues with equal-height bars sharing the same left boundary.

Quick: does the stack store heights or indices? Commit to your answer.

Common Belief: The stack stores bar heights for direct comparison.

Reality: The stack stores bar INDICES. Heights are retrieved as heights[index] for comparison, and indices are used to compute widths.

Why it matters: Storing heights loses position information — you cannot compute the left boundary width without knowing the actual index of the bar below in the stack.

Expert Zone

1

The algorithm handles all-equal heights correctly: all bars are pushed, then all are drained at the end. The last bar popped has left=-1 and right=n, giving the correct full-width rectangle.

2

For a strictly decreasing histogram [5,4,3,2,1], every bar triggers a pop chain. The maximum rectangle is the single widest bar at the lowest height — the algorithm finds this correctly in O(n).

3

The sentinel 0-height trick also handles the edge case of a single-bar histogram: push 0, sentinel triggers pop, area = heights[0] × 1 = heights[0], correct.

When NOT to use

If the problem asks for all rectangles (not just the maximum), this algorithm needs modification — it discards intermediate areas. For 2D variants (maximal rectangle in binary matrix), this algorithm is applied row by row, treating each row as a histogram.

Production Patterns

The monotonic stack pattern for largest rectangle appears in: (1) Image processing — finding the largest rectangular region in a binary image, (2) Database query optimization — estimating join cardinalities using histogram statistics, (3) Skyline problem — computing the silhouette of buildings using a similar stack technique.

Connections

Trapping Rain Water

Both use a monotonic stack (or two-pointer) to process bar heights and compute areas between bars — rain water fills concave regions while this problem maximizes rectangular spans.

The same stack invariant that finds rectangle widths in this problem finds water-holding depths in Trapping Rain Water — both exploit the 'nearest shorter bar' relationship.

Next Greater / Smaller Element

The pop trigger in this algorithm is identical to finding the 'next smaller element' for each bar — the element that pops a bar is its next smaller element and defines its right boundary.

Recognizing this as a 'next smaller element' problem lets you decompose it: precompute left and right boundaries separately using two monotonic stack passes, then compute areas — an alternative clean implementation.

Maximal Rectangle in Binary Matrix

This problem is the 1D base case. The 2D problem builds a histogram of consecutive 1s above each row and applies this exact algorithm to each row in sequence.

Mastering the 1D histogram solution is the prerequisite for the 2D problem — the 2D version is simply this algorithm applied n times to n different histograms.

Common Pitfalls

#1 Using top-1 as left boundary instead of stack top after pop.

Wrong approach:

int top = stack.Pop();
int left = top - 1; // WRONG — not the nearest shorter bar
int area = heights[top] * (i - left - 1);

Correct approach:

int top = stack.Pop();
int left = stack.Count > 0 ? stack.Peek() : -1; // Correct
int area = heights[top] * (i - left - 1);

Root cause:

The left boundary is not the adjacent bar but the nearest bar with smaller height — which is tracked by the stack, not by simple index arithmetic.

#2 Using 0 instead of -1 when stack is empty after pop.

Wrong approach:

int left = stack.Count > 0 ? stack.Peek() : 0; // WRONG
int area = heights[top] * (i - left - 1); // Off by 1

Correct approach:

int left = stack.Count > 0 ? stack.Peek() : -1; // Correct
int area = heights[top] * (i - left - 1);

Root cause:

When the stack is empty, the rectangle extends to the left edge — left boundary should be -1 so that width = i - (-1) - 1 = i, not i - 0 - 1 = i - 1.

#3 Forgetting to drain the stack after the main loop.

Wrong approach:

for (int i = 0; i < n; i++) {
while (stack.Count > 0 && heights[stack.Peek()] > heights[i]) {
int top = stack.Pop();
int left = stack.Count > 0 ? stack.Peek() : -1;
maxArea = Math.Max(maxArea, heights[top] * (i - left - 1));
}
stack.Push(i);
}
// WRONG — bars remaining in stack are never processed

Correct approach:

// After main loop, drain remaining bars with right = n
while (stack.Count > 0) {
int top = stack.Pop();
int left = stack.Count > 0 ? stack.Peek() : -1;
maxArea = Math.Max(maxArea, heights[top] * (n - left - 1));
}

Root cause:

Bars that are never smaller than any bar to their right remain in the stack after the main loop. Their right boundary is n (the end of the histogram), not any specific bar index.

Key Takeaways

The stack stores indices (not heights) in increasing height order — indices are needed for left boundary computation, heights are retrieved as heights[index].

When popping index 'top', the left boundary is stack.Peek() after popping (or -1 if empty), and the right boundary is the current index i that triggered the pop.

When the stack is empty after popping, use left = -1 (not 0) — the rectangle extends to the left edge and width = i - (-1) - 1 = i.

Always drain the stack after the main loop with right = n — bars that reach the end without being popped have the right edge as their right boundary.

The sentinel 0-height trick (append 0 to heights) eliminates the separate drain loop by triggering all remaining pops during the main loop.

Practice

1. What is the main purpose of using a stack in the Largest Rectangle in Histogram problem?

easy

A. To keep track of bars' indices with increasing heights

B. To store the heights of all bars directly

C. To sort the histogram bars by height

D. To reverse the order of histogram bars

Solution

1. Step 1: Understand stack usage in the problem

   The stack stores indices of bars in increasing order of their heights to help calculate areas efficiently.

2. Step 2: Why store indices, not heights?

   Indices allow calculation of width between bars when popping from the stack, which is essential for area calculation.

3. Final Answer:

   To keep track of bars' indices with increasing heights -> Option A

4. Quick Check:

   Stack stores indices for area calculation [OK]

Hint: Stack holds indices of increasing height bars [OK]

Common Mistakes:

• Storing heights instead of indices
• Using stack to sort bars
• Ignoring width calculation using indices

2. Which of the following C# code snippets correctly initializes a stack to store integers for the histogram problem?

easy

A. int[] stack = new int[10];

B. Stack stack = new Stack();

C. List<int> stack = new List<int>();

D. Stack<int> stack = new Stack<int>();

Solution

1. Step 1: Identify correct stack initialization in C#

   Using generic Stack<int> is the modern and type-safe way to create a stack for integers.

2. Step 2: Why not others?

   The non-generic Stack (like "Stack stack = new Stack();") uses the older style without type safety. A List (like "List<int> stack = new List<int>();") is not a stack. An array (like "int[] stack = new int[10];") is not a stack.

3. Final Answer:

   Stack<int> stack = new Stack<int>(); -> Option D

4. Quick Check:

   Generic Stack<int> is correct stack initialization [OK]

Hint: Use Stack<int> for integer stacks in C# [OK]

Common Mistakes:

• Using non-generic Stack without type safety
• Using List instead of Stack
• Using arrays instead of stack

3. What is the output of the following C# code snippet that calculates the largest rectangle area in histogram heights = [2, 1, 5, 6, 2, 3]?

int[] heights = {2, 1, 5, 6, 2, 3};
int largestRectangleArea(int[] heights) {
    Stack<int> stack = new Stack<int>();
    int maxArea = 0, i = 0;
    while (i < heights.Length) {
        if (stack.Count == 0 || heights[i] >= heights[stack.Peek()]) {
            stack.Push(i++);
        } else {
            int top = stack.Pop();
            int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, heights[top] * width);
        }
    }
    while (stack.Count > 0) {
        int top = stack.Pop();
        int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
        maxArea = Math.Max(maxArea, heights[top] * width);
    }
    return maxArea;
}

Console.WriteLine(largestRectangleArea(heights));

medium

A. 12

B. 10

C. 15

D. 9

Solution

1. Step 1: Trace the stack operations and area calculations

   For heights [2,1,5,6,2,3], the largest rectangle area is 10 (from bars 5 and 6 with width 2).

2. Step 2: Confirm final maxArea

   After processing all bars and stack cleanup, maxArea is 10.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest area is max height * width using stack [OK]

Common Mistakes:

• Miscomputing width when popping stack
• Forgetting to process remaining stack after loop
• Mixing up indices and heights

4. Identify the bug in this C# code snippet for Largest Rectangle in Histogram:

int largestRectangleArea(int[] heights) {
    Stack<int> stack = new Stack<int>();
    int maxArea = 0, i = 0;
    while (i <= heights.Length) {
        int currentHeight = (i == heights.Length) ? 0 : heights[i];
        if (stack.Count == 0 || currentHeight >= heights[stack.Peek()]) {
            stack.Push(i++);
        } else {
            int top = stack.Pop();
            int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, heights[top] * width);
        }
    }
    return maxArea;
}

medium

A. Width calculation misses subtracting 1, causing wrong area

B. Stack should store heights, not indices

C. Loop condition should be i < heights.Length, not <=

D. currentHeight assignment is incorrect

Solution

1. Step 1: Check width calculation formula

   Width should be i - stack.Peek() - 1 when stack is not empty, but code misses '-1'.

2. Step 2: Effect of missing '-1'

   Missing '-1' causes width to be larger than actual, leading to incorrect maxArea.

3. Final Answer:

   Width calculation misses subtracting 1, causing wrong area -> Option A

4. Quick Check:

   Width must subtract 1 for correct area [OK]

Hint: Subtract 1 in width calculation after popping stack [OK]

Common Mistakes:

• Forgetting to subtract 1 in width
• Using stack for heights instead of indices
• Incorrect loop boundary causing index errors

5. Given a histogram with heights = [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack approach? Explain how the stack helps find this area.

hard

A. 15

B. 10

C. 12

D. 8

Solution

1. Step 1: Use stack to track indices of increasing heights

   Push indices while heights increase; pop when current height is less, calculating area with popped height and width between indices.

2. Step 2: Calculate largest area for given heights

   For [6,2,5,4,5,1,6], largest rectangle area is 12 (from bars at indices 2,3,4 with min height 4 and width 3, calculated when popping index 3).

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Stack helps find max area = 12 [OK]

Hint: Stack finds max area by tracking increasing bars [OK]

Common Mistakes:

• Not popping all remaining bars after loop
• Incorrect width calculation
• Confusing heights and indices in stack