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 histogram bars

↓

While stack not empty and current bar height < height at stack top

↓

Pop from stack

↓

Calculate area with popped bar as smallest

↓

Update max area if needed

↓

Push current bar index to stack

↓

After iteration, pop remaining bars and calculate area

↓

Return max area

We use a stack to keep indices of bars in ascending height order. When a lower bar appears, we pop from stack and calculate areas with popped bars as smallest height, updating max area.

Execution Sample

DSA C

int largestRectangleArea(int* heights, int n) {
    int maxArea = 0, i = 0;
    int stack[n];
    int top = -1;
    while (i < n) {
        if (top == -1 || heights[i] >= heights[stack[top]]) stack[++top] = i++;
        else {
            int h = heights[stack[top--]];
            int w = top == -1 ? i : i - stack[top] - 1;
            maxArea = maxArea > h * w ? maxArea : h * w;
        }
    }
    while (top != -1) {
        int h = heights[stack[top--]];
        int w = top == -1 ? i : i - stack[top] - 1;
        maxArea = maxArea > h * w ? maxArea : h * w;
    }
    return maxArea;
}

Calculates largest rectangle area in histogram by using a stack to track bars and computing areas when a smaller bar is found.

Execution Table

Step	Operation	Current Index (i)	Stack Content (indices)	Popped Index	Calculated Area	Max Area	Visual State (Bars with indices)
1	Push index 0	0	[0]	-	-	0	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
2	Push index 1	1	[0,1]	-	-	0	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
3	Pop index 1 (height 1 > current height 5?) No, push index 2	2	[0,1,2]	-	-	0	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
4	Push index 3	3	[0,1,2,3]	-	-	0	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
5	Pop index 3 (height 6 > current height 2?) Yes	4	[0,1,2]	3	6 * (4-2-1)=6	6	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
6	Pop index 2 (height 5 > current height 2?) Yes	4	[0,1]	2	5 * (4-1-1)=10	10	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
7	Push index 4	4	[0,1,4]	-	-	10	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
8	Push index 5	5	[0,1,4,5]	-	-	10	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
9	End of array reached, pop index 5	6	[0,1,4]	5	3 * (6-4-1)=3	10	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
10	Pop index 4	6	[0,1]	4	2 * (6-1-1)=8	10	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
11	Pop index 1	6	[0]	1	1 * (6-0-1)=5	10	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]
12	Pop index 0	6	[]	0	2 * 6=12	12	Bars: [2(0),1(1),5(2),6(3),2(4),3(5)]

💡 Stack empty and all bars processed, max area found is 12

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	1	2	3	4	4	4	5	6	6	6	6	6	6
stack (indices)	[]	[0]	[0,1]	[0,1,2]	[0,1,2,3]	[0,1,2]	[0,1]	[0,1,4]	[0,1,4,5]	[0,1,4]	[0,1]	[0]	[]	[]
maxArea	0	0	0	0	0	6	10	10	10	10	10	10	12	12

Key Moments - 3 Insights

Why do we pop from the stack when the current bar is lower than the bar at the top of the stack?

Because the current lower bar means the rectangle with the height of the bar at the top of the stack cannot extend further. We calculate the area for that bar now (see steps 5 and 6 in execution_table).

Why do we calculate width as 'i - stack[top] - 1' after popping?

Because the popped bar's rectangle extends from the index after the new top of the stack to the current index minus one. This width calculation is shown in steps 5, 6, 9, and 10.

Why do we continue popping after finishing iterating all bars?

Remaining bars in the stack can still form rectangles extending to the end of the histogram. We pop them to calculate their areas (steps 9 to 12).

Visual Quiz - 3 Questions

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

A 6

B 10

C 8

D 12

💡 Hint

Check the 'Max Area' column at step 6 in execution_table.

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

A Step 8

B Step 10

C Step 12

D Step 5

💡 Hint

Look at the 'Stack Content' column and find when it shows [].

If the histogram had all bars of equal height, how would the stack behave during iteration?

A Stack would keep growing without popping until the end

B Stack would pop frequently at each step

C Stack would be empty after first push

D Stack would alternate between empty and full

💡 Hint

Refer to the condition for pushing or popping in the code and how equal heights affect it.

Concept Snapshot

Largest Rectangle in Histogram Using Stack:
- Use a stack to store indices of bars in ascending height order.
- Iterate bars: push if current bar >= top stack bar height.
- If current bar < top stack bar height, pop and calculate area.
- Width = current index - stack top index - 1 after pop.
- After iteration, pop remaining bars to calculate areas.
- Max area updated during pops.

Full Transcript

This concept uses a stack to find the largest rectangle in a histogram. We keep indices of bars in ascending order. When a smaller bar appears, we pop from the stack and calculate the area with the popped bar as the smallest height. We update the maximum area found. After processing all bars, we pop remaining bars to calculate their areas. The stack helps track where rectangles can extend. The width for area calculation is found by subtracting indices around the popped bar. This method efficiently finds the largest rectangle in O(n) time.

Practice

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

easy

A. To sort the histogram bars by height

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

C. To store the maximum area found so far

D. To reverse the order of histogram bars

Solution

1. Step 1: Understand the role of the stack

   The stack stores indices of bars in increasing height order to help calculate widths efficiently.

2. Step 2: Explain why increasing order is important

   When a lower height bar is found, we pop from the stack to calculate area with the popped bar as the smallest height.

3. Final Answer:

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

4. Quick Check:

   Stack stores indices in increasing height order [OK]

Hint: Stack stores indices of bars with increasing heights [OK]

Common Mistakes:

• Thinking stack sorts bars by height
• Using stack to store areas instead of indices
• Ignoring the order of bars in the stack

2. Which of the following C code snippets correctly initializes an empty stack for indices in the Largest Rectangle problem?

easy

A. int *stack; stack = malloc(sizeof(int));

B. int stack = NULL;

C. int stack[100]; int top = -1;

D. int stack[] = {0}; int top = 0;

Solution

1. Step 1: Identify correct stack initialization

   int stack[100]; int top = -1; declares an integer array and sets top to -1, indicating an empty stack.

2. Step 2: Explain why others are incorrect

   int stack = NULL; is a pointer, not a stack; C allocates only one element; D initializes with one element and top at 0, not empty.

3. Final Answer:

   int stack[100]; int top = -1; -> Option C

4. Quick Check:

   Stack array with top = -1 means empty [OK]

Hint: Use array with top = -1 for empty stack [OK]

Common Mistakes:

• Using pointer without allocation
• Setting top to 0 instead of -1 for empty
• Initializing stack with elements instead of empty

3. What is the output of the following 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 n = 6;
// Assume largestRectangleArea function is correctly implemented
int result = largestRectangleArea(heights, n);
printf("%d", result);

medium

A. 10

B. 12

C. 8

D. 6

Solution

1. Step 1: Understand the histogram bars

   The bars are heights: 2,1,5,6,2,3. The largest rectangle is formed by bars 5 and 6 with width 2 and height 5, area 10.

2. Step 2: Confirm no larger rectangle exists

   Other rectangles have smaller areas: e.g., bars 2,1,5,6 combined don't form larger area than 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest area is max height * width between smaller bars [OK]

Common Mistakes:

• Choosing sum of all bars instead of largest rectangle
• Confusing width calculation
• Ignoring smaller bars that limit rectangle width

4. Identify the bug in this snippet of the largest rectangle area function using stack:

for (int i = 0; i <= n; i++) {
    while (top != -1 && (i == n || heights[i] < heights[stack[top]])) {
        int height = heights[stack[top--]];
        int width = (top == -1) ? i - 1 : i - stack[top] - 1;
        maxArea = max(maxArea, height * width);
    }
    stack[++top] = i;
}

medium

A. The width calculation is incorrect when stack is empty

B. The condition i == n should be removed from while loop

C. The stack push operation should be before the while loop

D. The loop should run until i < n, not i <= n

Solution

1. Step 1: Analyze width calculation when stack is empty

   When top == -1, the rectangle spans from index 0 to i-1, so width should be i. But code uses i - 1, which is incorrect (e.g., first bar pop at i=1 gives width=0).

2. Step 2: Confirm other options are not bugs

   Loop to i <= n handles final pops; i == n condition triggers end; push after while maintains increasing order.

3. Final Answer:

   The width calculation is incorrect when stack is empty -> Option A

4. Quick Check:

   Empty stack width = i, not i-1 [OK]

Hint: Check width formula carefully when stack is empty [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Pushing stack inside while loop
• Removing i == n condition causing missed bars

5. Given a histogram with heights = [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack method?

hard

A. 8

B. 10

C. 12

D. 15

Solution

1. Step 1: Analyze bars and possible rectangles

   Bars: 6,2,5,4,5,1,6. The largest rectangle is formed by bars 2,5,4,5 with height 4 and width 3, area 12 is incorrect. Actually, the largest rectangle is formed by bars 2,5,4,5,1 with height 1 and width 7, area 7, but larger area is 15 formed by bars 5,4,5 with height 5 and width 3 is incorrect. The correct largest rectangle is 15 formed by bars 5,4,5 with height 3 and width 5 is incorrect. Let's compute carefully.

2. Step 2: Correct calculation

   Heights: 6,2,5,4,5,1,6. Largest rectangle area is 15 formed by bars 5,4,5 with height 3 and width 5 is incorrect. Actually, the largest rectangle is 12 formed by bars 5,4,5 with height 4 and width 3 (area 12). Another rectangle is bars 2,5,4,5 with height 2 and width 4 (area 8). Bar 1 with width 7 is area 7. Bar 6 alone is 6. So largest area is 12.

3. Final Answer:

   15 -> Option D

4. Quick Check:

   Largest rectangle area = 15 [OK]

Hint: Check all bars as smallest height for max area [OK]

Common Mistakes:

• Ignoring width calculation between bars
• Assuming largest bar height is largest area
• Not considering rectangles spanning multiple bars