Largest Rectangle in Histogram Using Stack in DSA C#

Mental Model

We use a stack to keep track of bars that are not yet processed for the largest rectangle. When we find a bar shorter than the top of the stack, we calculate areas with the bars popped from the stack.

Analogy: Imagine stacking books by height. When a shorter book comes, you remove taller books from the stack to find the biggest flat surface you can make with the books below.

Histogram bars: height
  _     _  _  _
 | |   | || || |
 | | _ | || || |
 | || || || || |
 | || || || || |
 0  1  2  3  4  (indices)
Stack stores indices of bars in increasing height order.

Dry Run Walkthrough

Input: histogram heights: [2, 1, 5, 6, 2, 3]

Goal: Find the largest rectangle area that can be formed in the histogram

Step 1: Push index 0 (height 2) onto stack

Stack: [0]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Start with first bar to build increasing height stack

Step 2: Height at index 1 (1) is less than height at stack top index 0 (2), pop 0 and calculate area

Popped index 0 (height 2), width = 1 (since stack empty), area = 2*1=2
Stack: []
Push index 1

Why: Found smaller bar, so calculate area with taller bars before it

Step 3: Push index 1 (height 1) onto stack

Stack: [1]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Keep stack increasing, now with height 1

Step 4: Push index 2 (height 5) onto stack

Stack: [1, 2]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Height 5 is greater than top height 1, so push

Step 5: Push index 3 (height 6) onto stack

Stack: [1, 2, 3]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Height 6 is greater than top height 5, so push

Step 6: Height at index 4 (2) is less than height at stack top index 3 (6), pop 3 and calculate area

Popped index 3 (height 6), width = 1 (index 4 - index 2 - 1), area = 6*1=6
Stack: [1, 2]

Why: Calculate area for bar 6 as current bar is smaller

Step 7: Height at index 4 (2) is less than height at stack top index 2 (5), pop 2 and calculate area

Popped index 2 (height 5), width = 2 (index 4 - index 1 - 1), area = 5*2=10
Stack: [1]

Why: Calculate area for bar 5 as current bar is smaller

Step 8: Push index 4 (height 2) onto stack

Stack: [1, 4]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Push current bar after popping taller bars

Step 9: Push index 5 (height 3) onto stack

Stack: [1, 4, 5]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3 -> null

Why: Height 3 is greater than top height 2, so push

Step 10: Reached end, pop remaining bars and calculate areas

Pop index 5 (height 3), width = 1 (6 - 4 - 1), area = 3*1=3
Pop index 4 (height 2), width = 4 (6 - 1 - 1), area = 2*4=8
Pop index 1 (height 1), width = 6 (6 - (-1) - 1), area = 1*6=6
Stack: []

Why: Calculate areas for remaining bars after full traversal

Result:

Largest rectangle area = 10
Final stack empty

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Histogram {
    public static int LargestRectangleArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int i = 0;
        while (i < heights.Length) {
            if (stack.Count == 0 || heights[i] >= heights[stack.Peek()]) {
                stack.Push(i); // push index of current bar
                i++;
            } else {
                int top = stack.Pop(); // pop top
                int width = stack.Count == 0 ? i : i - stack.Peek() - 1; // calculate width
                int area = heights[top] * width; // calculate area
                if (area > maxArea) maxArea = area; // update max
            }
        }
        while (stack.Count > 0) {
            int top = stack.Pop();
            int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
            int area = heights[top] * width;
            if (area > maxArea) maxArea = area;
        }
        return maxArea;
    }

    static void Main() {
        int[] histogram = {2, 1, 5, 6, 2, 3};
        int result = LargestRectangleArea(histogram);
        Console.WriteLine(result);
    }
}

if (stack.Count == 0 || heights[i] >= heights[stack.Peek()]) { stack.Push(i); // push index of current bar i++;

push current bar index if stack empty or current bar taller or equal to top bar

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

pop top bar and calculate area with width between current index and new stack top

while (stack.Count > 0) { int top = stack.Pop(); int width = stack.Count == 0 ? i : i - stack.Peek() - 1; int area = heights[top] * width; if (area > maxArea) maxArea = area; }

after full traversal, pop remaining bars and calculate areas

Output

10

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once

Space: O(n) for the stack that stores indices of bars

vs Alternative: Naive approach checks all pairs for largest rectangle with O(n^2) time, stack method is much faster

Edge Cases

empty histogram

returns 0 as no bars exist

DSA C#

while (i < heights.Length) { ... } handles zero length by skipping loop

all bars same height

largest rectangle is height * number of bars

DSA C#

stack.Push(i) when heights[i] >= heights[stack.Peek()] keeps all bars in stack

strictly increasing heights

all bars pushed, largest rectangle is last bar height * total bars

DSA C#

stack.Push(i) when heights[i] >= heights[stack.Peek()]

strictly decreasing heights

bars popped frequently to calculate areas, largest rectangle found during pops

DSA C#

else block with stack.Pop() calculates areas when current bar smaller

When to Use This Pattern

When asked to find the largest rectangle in a histogram or largest area under a curve, use the stack pattern to track increasing heights and calculate areas efficiently.

Common Mistakes

Mistake: Using heights values directly in stack instead of indices
Fix: Store indices in stack to calculate widths correctly

Mistake: Not calculating width correctly when stack is empty after pop
Fix: Use width = current index if stack empty, else current index - stack top - 1

Mistake: Not processing remaining bars in stack after full traversal
Fix: Add final while loop to pop and calculate areas for remaining bars

Summary

Finds the largest rectangle area in a histogram using a stack to track bars.

Use when you need to find max rectangle area under histogram bars efficiently.

The key is to use a stack to keep indices of bars in increasing order and calculate areas when a smaller bar appears.

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