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 by index

↓

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 index to stack

↓

After iteration, pop remaining bars

↓

Calculate area for each popped bar

↓

Update max area if needed

↓

Return max area

We scan bars left to right, using a stack to keep indexes of bars in ascending height order. When a lower bar appears, we pop taller bars to calculate areas, updating max area.

Execution Sample

DSA C++

int largestRectangleArea(vector<int>& heights) {
  stack<int> s;
  int maxArea = 0, i = 0;
  while (i < heights.size()) {
    if (s.empty() || heights[i] >= heights[s.top()]) s.push(i++);
    else {
      int h = heights[s.top()]; s.pop();
      int w = s.empty() ? i : i - s.top() - 1;
      maxArea = max(maxArea, h * w);
    }
  }
  while (!s.empty()) {
    int h = heights[s.top()]; s.pop();
    int w = s.empty() ? i : i - s.top() - 1;
    maxArea = max(maxArea, h * w);
  }
  return maxArea;
}

Calculates largest rectangle area in histogram by pushing indexes of bars in ascending order and popping when a smaller bar is found to compute areas.

Execution Table

Step	Operation	Current Index i	Stack Content (indexes)	Popped Index	Calculated Area	Max Area	Visual State (Bars with stack top)
1	Start iteration	0	[]	-	-	0	Bars: [2,2,5,6,2,3], Stack: empty
2	Push index 0	1	[0]	-	-	0	Stack top index 0 (height 2)
3	Push index 1	2	[0,1]	-	-	0	Stack top index 1 (height 2)
4	Current height 5 >= height at stack top (2), push index 2	3	[0,1,2]	-	-	0	Stack top index 2 (height 5)
5	Current height 6 >= height at stack top (5), push index 3	4	[0,1,2,3]	-	-	0	Stack top index 3 (height 6)
6	Current height 2 < height at stack top (6), pop index 3	4	[0,1,2]	3	6 * (4-2-1)=6	6	Popped bar height 6, width 1
7	Current height 2 < height at stack top (5), pop index 2	4	[0,1]	2	5 * (4-1-1)=10	10	Popped bar height 5, width 2
8	Current height 2 >= height at stack top (2), push index 4	5	[0,1,4]	-	-	10	Stack top index 4 (height 2)
9	Current height 3 >= height at stack top (2), push index 5	6	[0,1,4,5]	-	-	10	Stack top index 5 (height 3)
10	End of array reached, pop index 5	6	[0,1,4]	5	3 * (6-4-1)=3	10	Popped bar height 3, width 1
11	Pop index 4	6	[0,1]	4	2 * (6-1-1)=8	10	Popped bar height 2, width 4
12	Pop index 1	6	[0]	1	2 * (6-0-1)=10	10	Popped bar height 2, width 5
13	Pop index 0	6	[]	0	2 * 6=12	12	Popped bar height 2, width 6
14	Done	6	[]	-	-	12	Final max area 12

💡 All bars processed and stack emptied, max area found is 12

Variable Tracker

Variable	Start	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	After Step 13	Final
i	0	1	2	3	4	4	4	5	6	6	6	6	6	6
stack	[]	[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 height is less than the height at the stack top?

Because the current bar limits the width of rectangles with taller bars on the stack. Popping lets us calculate the largest rectangle possible with those taller bars as the smallest height (see steps 6 and 7 in execution_table).

How do we calculate the width of the rectangle when popping a bar from the stack?

Width is the distance between the current index and the index now at the top of the stack minus one. If the stack is empty, width is the current index itself (see steps 6,7,11,13).

Why do we continue popping after finishing iterating all bars?

Remaining bars in the stack have no smaller bar to the right, so we calculate areas assuming the right boundary is the end of the histogram (see steps 10 to 13).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the calculated area and which bar index was popped?

A Area 6, popped index 3

B Area 10, popped index 2

C Area 8, popped index 4

D Area 3, popped index 5

💡 Hint

Check the 'Calculated Area' and 'Popped Index' columns at step 7 in execution_table

At which step does the max area update to 12?

A Step 13

B Step 10

C Step 6

D Step 9

💡 Hint

Look at the 'Max Area' column in execution_table and find when it changes to 12

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

A Stack would remain empty

B Stack would pop frequently during iteration

C Stack would keep all indexes until the end, then pop all

D Stack would only hold one index at a time

💡 Hint

Refer to variable_tracker stack values and how pushing happens when current height >= stack top height

Concept Snapshot

Largest Rectangle in Histogram Using Stack
- Use a stack to store indexes of bars in ascending height order
- Iterate bars, push if current bar taller or equal
- Pop when current bar shorter, calculate area with popped bar as smallest
- After iteration, pop remaining bars to calculate areas
- Track max area during pops
- Width calculation depends on current index and stack top

Full Transcript

This visualization shows how to find the largest rectangle in a histogram using a stack. We scan bars left to right, pushing indexes of bars that are taller or equal to the previous. When a shorter bar appears, we pop from the stack to calculate areas of rectangles with popped bars as the smallest height. We update the maximum area found. After processing all bars, we pop remaining bars to calculate any remaining areas. The stack helps track boundaries for width calculation. The largest area found in the example is 12.

Practice

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

easy

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

B. To store the heights of all bars in sorted order

C. To reverse the order of histogram bars

D. To count the total number of bars in the histogram

Solution

1. Step 1: Understand the role of stack in the problem

   The stack is used to store indices of bars in increasing order of their heights to efficiently calculate areas.

2. Step 2: Why increasing order indices?

   When a bar with smaller height is found, we pop from the stack to calculate the largest rectangle possible with the popped bar as the smallest height.

3. Final Answer:

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

4. Quick Check:

   Stack stores indices in increasing height order = A [OK]

Hint: Stack stores indices of increasing height bars for area calculation [OK]

Common Mistakes:

• Thinking stack stores heights instead of indices
• Assuming stack sorts bars by height
• Using stack to count bars instead of tracking indices

2. Which of the following C++ code snippets correctly initializes an empty stack to store indices for the histogram bars?

easy

A. stack<int> s = new stack<int>();

B. stack s<int>;

C. stack<int> s;

D. stack<int> s[];

Solution

1. Step 1: Check correct stack declaration syntax in C++

   The correct way to declare an empty stack of integers is stack<int> s;.

2. Step 2: Identify errors in other options

   stack<int> s = new stack<int>(); uses 'new' which is incorrect for stack initialization. stack s<int>; has wrong template syntax. stack<int> s[]; declares an array of stacks, not a single stack.

3. Final Answer:

   stack<int> s; -> Option C

4. Quick Check:

   Correct stack declaration = C [OK]

Hint: Use stack<int> s; to declare empty stack of integers [OK]

Common Mistakes:

• Using 'new' keyword incorrectly with stack
• Wrong template syntax like stack s<int>
• Declaring array of stacks instead of single stack

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 largestRectangleArea(vector<int>& heights) {
    stack<int> s;
    int max_area = 0, i = 0;
    while (i < heights.size()) {
        if (s.empty() || heights[i] >= heights[s.top()]) {
            s.push(i++);
        } else {
            int tp = s.top(); s.pop();
            int area = heights[tp] * (s.empty() ? i : i - s.top() - 1);
            max_area = max(max_area, area);
        }
    }
    while (!s.empty()) {
        int tp = s.top(); s.pop();
        int area = heights[tp] * (s.empty() ? i : i - s.top() - 1);
        max_area = max(max_area, area);
    }
    return max_area;
}

cout << largestRectangleArea({2,1,5,6,2,3});

medium

A. 12

B. 10

C. 8

D. 6

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 max_area value

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

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest rectangle area for example histogram is 10 [OK]

Common Mistakes:

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

4. Identify the bug in the following code snippet for Largest Rectangle in Histogram:

int largestRectangleArea(vector<int>& heights) {
    stack<int> s;
    int max_area = 0, i = 0;
    while (i < heights.size()) {
        if (s.empty() || heights[i] >= heights[s.top()]) {
            s.push(i++);
        } else {
            int tp = s.top(); s.pop();
            int area = heights[tp] * (s.empty() ? i : i - s.top() - 1);
            max_area = max(max_area, area);
        }
    }
    while (!s.empty()) {
        int tp = s.top(); s.pop();
        int area = heights[tp] * (s.empty() ? i : i - s.top() - 1);
        max_area = max(max_area, area);
    }
    return max_area;
}

medium

A. Width calculation misses subtracting 1 from index difference

B. Missing increment of i in else block

C. Stack is not initialized properly

D. Incorrect comparison operator in if condition

Solution

1. Step 1: Analyze width calculation formula

   The width should be i - s.top() - 1 but code uses i - s.top(), missing the '-1'.

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

   This causes overestimation of width and incorrect area calculation.

3. Final Answer:

   Width calculation misses subtracting 1 from index difference -> Option A

4. Quick Check:

   Width = i - s.top() - 1 needed [OK]

Hint: Subtract 1 when calculating width between indices [OK]

Common Mistakes:

• Using i - s.top() instead of i - s.top() - 1
• Not incrementing i in else block (but here it is correct)
• Wrong comparison operator in if condition

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 in finding this area.

hard

A. 12

B. 8

C. 10

D. 15

Solution

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

   Push indices while heights increase: indices 0(6), then 1(2) triggers pop of 0, area=6*1=6. Continue pushing and popping to calculate areas.

2. Step 2: Calculate max area by popping stack when current height is less

   Largest rectangle area found is 15 (from bars at indices 2,3,4 with min height 5 and width 3).

3. Final Answer:

   15 -> Option D

4. Quick Check:

   Largest rectangle area = 15 [OK]

Hint: Stack helps find max area by tracking increasing heights and widths [OK]

Common Mistakes:

• Not popping stack correctly when height decreases
• Incorrect width calculation during area computation
• Ignoring last stack cleanup after main loop