Largest Rectangle in Histogram Using Stack in DSA C# - Execution Trace

Concept Flow - Largest Rectangle in Histogram Using Stack

Start with empty stack

↓

Iterate over bars

↓

If stack empty or current bar taller

↓

Push index

↓

Calculate area with popped bar

↓

After iteration, pop remaining bars

↓

Calculate max area

↓

Done

We use a stack to keep indexes of bars in increasing height order. When a lower bar appears, we pop from stack and calculate area with popped bar as smallest height. After processing all bars, we pop remaining bars to find max area.

Execution Sample

DSA C#

int[] heights = {2, 1, 5, 6, 2, 3};
Stack<int> stack = new Stack<int>();
int maxArea = 0;
for (int i = 0; i <= heights.Length; i++) {
  int h = (i == heights.Length) ? 0 : heights[i];

This code iterates over histogram bars, using a stack to find largest rectangle area by popping bars when a smaller height is found.

Execution Table

Step	Operation	Current Index (i)	Stack Content (indexes)	Height at i	Action	Max Area	Visual State
1	Start iteration	0	[]	2	Stack empty, push 0	0	[2]
2	Next bar	1	[0]	1	Height 1 < height at stack top 2, pop 0 and calculate area	2	Pop index 0, area=2*1=2
3	Push current index	1	[]	1	Push 1	2	[1]
4	Next bar	2	[1]	5	Height 5 > height at stack top 1, push 2	2	[1,5]
5	Next bar	3	[1,2]	6	Height 6 > height at stack top 5, push 3	2	[1,5,6]
6	Next bar	4	[1,2,3]	2	Height 2 < height at stack top 6, pop 3 and calculate area	6	Pop 3, area=6*1=6
7	Check again	4	[1,2]	2	Height 2 < height at stack top 5, pop 2 and calculate area	10	Pop 2, area=5*2=10
8	Push current index	4	[1]	2	Push 4	10	[1,2]
9	Next bar	5	[1,4]	3	Height 3 > height at stack top 2, push 5	10	[1,2,3]
10	End of array	6	[1,4,5]	0	Pop 5 and calculate area	10	Pop 5, area=3*1=3
11	Pop next	6	[1,4]	0	Pop 4 and calculate area	10	Pop 4, area=2*4=8
12	Pop next	6	[1]	0	Pop 1 and calculate area	10	Pop 1, area=1*6=6
13	Stack empty	6	[]	0	Done	10	Max area found is 10

💡 Reached end of histogram and stack is empty, max area is 10

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	Final
i	0	0	1	1	2	3	4	4	5	6	6	6	6	6
stack	[]	[0]	[]	[1]	[1,2]	[1,2,3]	[1,2]	[1]	[1,4]	[1,4,5]	[1,4]	[1]	[]	[]
maxArea	0	0	2	2	2	2	6	10	10	10	10	10	10	10

Key Moments - 3 Insights

Why do we pop from the stack when the current bar is shorter than the bar at the stack's top?

Because the current shorter bar means the previous taller bars cannot extend further to the right. We calculate the area with the popped bar as the smallest height using the current index as the right boundary (see steps 2, 6, and 7 in execution_table).

Why do we push the current index after popping bars?

After popping taller bars, the current bar's index is pushed to mark the start of a new potential rectangle with this height or taller bars ahead (see steps 3, 8, and 9).

Why do we add a bar of height 0 at the end (i == heights.Length)?

This forces popping all remaining bars in the stack to calculate areas for rectangles that extend to the end of the histogram (see steps 10-12).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the maxArea after popping index 2?

A 6

B 10

C 8

D 2

💡 Hint

Check the 'Max Area' column at step 7 in execution_table

At which step does the stack become empty for the first time after starting?

A Step 3

B Step 8

C Step 2

D Step 13

💡 Hint

Look at the 'Stack Content' column in execution_table to find when it first becomes []

If the last bar height was increased instead of 3, how would the maxArea change?

A It would increase

B It would decrease

C It would stay 10

D It would become 0

💡 Hint

Consider how a taller last bar affects the area calculations in the final popping steps (see variable_tracker and execution_table)

Concept Snapshot

Largest Rectangle in Histogram Using Stack:
- Use a stack to store indexes of bars in increasing height.
- For each bar, pop while current bar is shorter than stack top.
- Calculate area with popped bar as smallest height.
- Push current index after popping.
- After iteration, pop remaining bars to find max area.
- Time complexity: O(n).

Full Transcript

This concept uses a stack to find the largest rectangle in a histogram. We iterate over each bar, pushing indexes when bars are taller or equal to the stack top. When a shorter bar appears, we pop from the stack and calculate areas using popped bars as the smallest height. We continue until all bars are processed, then pop remaining bars to calculate areas extending to the end. The maximum area found during these steps is the answer. The stack helps track boundaries efficiently, making the algorithm run in linear time.

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