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 the area with the top bar as the smallest height.

Analogy: Imagine stacking books by height. When you find a shorter book, you remove taller books from the stack and calculate the largest flat surface you can make with those books before placing the shorter one.

Histogram bars: height
  6 |       ■
  5 |   ■   ■
  4 |   ■ ■ ■
  3 | ■ ■ ■ ■
  2 | ■ ■ ■ ■
  1 | ■ ■ ■ ■
    +---------
      0 1 2 3 4  (indices)
Stack: stores indices of bars in increasing height order -> [0,1,2,...]

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

Why: Start with first bar to build increasing height stack

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

Popped index 0 (height 2), stack empty
Area = height 2 * width 1 = 2
Push index 1 (height 1)

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

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

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

Why: Height 5 is greater than top height 1, keep increasing stack

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

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

Why: Height 6 is greater than top height 5, continue increasing stack

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

Popped index 3 (height 6), stack: [1, 2]
Area = height 6 * width 1 = 6

Why: Smaller bar found, calculate area for taller bar

Step 6: Current bar height 2 is less than height at stack top (5), pop index 2 and calculate area

Popped index 2 (height 5), stack: [1]
Area = height 5 * width 2 = 10

Why: Continue popping taller bars to find max area

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

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

Why: Height 2 is greater than top height 1, push to stack

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

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

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

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

Pop index 5 (height 3), area = 3 * 1 = 3
Pop index 4 (height 2), area = 2 * 4 = 8
Pop index 1 (height 1), area = 1 * 6 = 6

Why: Calculate areas for remaining bars to find max

Result:

Largest rectangle area = 10
Final stack empty

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    stack<int> s; // stores indices
    int max_area = 0;
    int n = heights.size();
    for (int i = 0; i <= n; i++) {
        int curr_height = (i == n) ? 0 : heights[i];
        while (!s.empty() && curr_height < heights[s.top()]) {
            int height = heights[s.top()];
            s.pop();
            int width = s.empty() ? i : i - s.top() - 1;
            int area = height * width;
            if (area > max_area) max_area = area;
        }
        s.push(i);
    }
    return max_area;
}

int main() {
    vector<int> histogram = {2, 1, 5, 6, 2, 3};
    cout << largestRectangleArea(histogram) << endl;
    return 0;
}

for (int i = 0; i <= n; i++) {

iterate through all bars plus one extra to flush stack

int curr_height = (i == n) ? 0 : heights[i];

use 0 height at end to pop all remaining bars

while (!s.empty() && curr_height < heights[s.top()]) {

pop bars taller than current to calculate area

int height = heights[s.top()]; s.pop();

get height of bar to calculate area

int width = s.empty() ? i : i - s.top() - 1;

calculate width of rectangle using stack top

if (area > max_area) max_area = area;

update max area if current area is larger

s.push(i);

push current index to stack to maintain increasing heights

Output

10

Complexity Analysis

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

Space: O(n) for the stack storing 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++

int n = heights.size(); for (int i = 0; i <= n; i++) {

all bars same height

calculates area as height * number of bars

DSA C++

while (!s.empty() && curr_height < heights[s.top()]) {

strictly increasing heights

stack grows until end, then popped to calculate max area

DSA C++

int curr_height = (i == n) ? 0 : heights[i];

When to Use This Pattern

When asked to find the largest rectangle in a histogram or similar problem, use a stack to track increasing heights and calculate areas when a smaller height appears.

Common Mistakes

Mistake: Not pushing the extra index at the end to flush the stack
Fix: Add an iteration with height 0 after the last bar to pop all remaining bars

Mistake: Calculating width incorrectly by not considering stack emptiness
Fix: Use width = i if stack empty else i - s.top() - 1

Summary

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

Use when you need to efficiently find max rectangle area in bar charts or histograms.

The key insight is to use a stack to maintain increasing heights 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 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