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.