Largest Rectangle in Histogram Using Stack in DSA C++ - Deep Dive

Overview - Largest Rectangle in Histogram Using Stack

What is it?

The Largest Rectangle in Histogram problem asks us to find the biggest rectangle that can fit inside a histogram made of bars of different heights. Each bar has a width of 1 unit. We want to find the area of the largest rectangle that can be formed by one or more consecutive bars. This problem helps us understand how to use stacks to solve range and boundary problems efficiently.

Why it matters

Without this method, finding the largest rectangle would require checking every possible group of bars, which takes a lot of time and is slow for big histograms. Using a stack makes the process much faster and practical for real-world problems like image processing, stock span, or land area calculations. Without this, many applications would be inefficient and slow.

Where it fits

Before this, learners should understand arrays and basic stack operations. After this, they can explore more complex stack problems, segment trees, or dynamic programming techniques for range queries.

Mental Model

Core Idea

Use a stack to keep track of bars in increasing height order so that when a shorter bar appears, you can calculate the largest rectangle possible with the taller bars before it.

Think of it like...

Imagine stacking books by height on a shelf from shortest to tallest. When you find a shorter book, you remove taller books one by one to see how much space they cover together before placing the shorter book.

Histogram bars: heights = [2, 1, 5, 6, 2, 3]
Stack stores indices of bars with increasing heights.

Initial: stack empty
Push index 0 (height 2): stack = [0]
Push index 1 (height 1): height 1 < height 2, pop 0, calculate area
Push index 1: stack = [1]
Push index 2 (height 5): stack = [1, 2]
Push index 3 (height 6): stack = [1, 2, 3]
Push index 4 (height 2): height 2 < height 6, pop 3, calculate area
Pop 2, calculate area
Push 4: stack = [1, 4]
Push index 5 (height 3): stack = [1, 4, 5]
End: pop remaining and calculate areas

Stack helps find left and right boundaries for each bar.

Build-Up - 7 Steps

1

Foundation

Understanding Histogram and Rectangle Area

Concept: Learn what a histogram is and how rectangles form inside it.

A histogram is a set of bars placed side by side. Each bar has a height and width 1. The rectangle area inside the histogram is height x width. For example, if a bar has height 4 and width 1, its area is 4. If two bars of height 4 are next to each other, the combined rectangle area is 4 x 2 = 8.

Result

You understand how to calculate area of single and multiple bars combined.

Knowing how area is calculated helps you see why combining bars matters for finding the largest rectangle.

2

Foundation

Basic Stack Operations and Their Use

Concept: Learn how a stack works and why it helps track bars.

A stack is a data structure where you add (push) and remove (pop) items in last-in, first-out order. For this problem, we use a stack to keep track of bar indices with increasing heights. When a new bar is shorter, we pop from the stack to calculate areas for taller bars.

Result

You can push and pop bar indices to track increasing heights.

Understanding stack behavior is key to efficiently finding boundaries for rectangles.

3

Intermediate

Using Stack to Find Left Boundaries

🤔Before reading on: do you think we can find the left boundary of each bar by scanning from left to right without extra space? Commit to yes or no.

Concept: Use the stack to find the nearest smaller bar to the left for each bar.

We scan bars from left to right. For each bar, we pop from the stack while the top bar is taller or equal. The top of the stack after popping is the index of the nearest smaller bar to the left. If stack is empty, no smaller bar to the left exists. We then push the current bar index.

Result

We get left boundaries for all bars in one pass.

Knowing left boundaries helps limit how far a rectangle can extend to the left.

4

Intermediate

Using Stack to Find Right Boundaries

🤔Before reading on: do you think right boundaries can be found in the same pass as left boundaries? Commit to yes or no.

Concept: Use a similar stack approach scanning from right to left to find nearest smaller bars on the right.

We scan bars from right to left. For each bar, we pop from the stack while the top bar is taller or equal. The top of the stack after popping is the index of the nearest smaller bar to the right. If stack is empty, no smaller bar to the right exists. We then push the current bar index.

Result

We get right boundaries for all bars in one pass.

Knowing right boundaries helps limit how far a rectangle can extend to the right.

5

Intermediate

Calculating Maximum Rectangle Area

Concept: Combine left and right boundaries to calculate max area for each bar.

For each bar, the width of the largest rectangle is (right boundary - left boundary - 1). Multiply this width by the bar's height to get the area. Track the maximum area found.

Result

You can find the largest rectangle area in the histogram.

Combining boundaries with height gives the exact largest rectangle for each bar.

6

Advanced

Single Pass Stack Algorithm

🤔Before reading on: do you think it's possible to find the largest rectangle in one pass using a stack? Commit to yes or no.

Concept: Use one stack pass to find max area by pushing indices and popping when current bar is shorter.

Initialize an empty stack. Iterate over bars: - While stack not empty and current bar height < height at stack top, pop stack top. - Calculate area with popped bar as smallest height: width = current index - stack top index - 1 (or current index if stack empty). - Push current index. After iteration, pop remaining bars and calculate areas similarly. This finds max rectangle in O(n) time.

Result

Largest rectangle area is found efficiently in one pass.

One pass stack method is optimal and elegant, avoiding separate boundary arrays.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: do you think adding a zero-height bar at the end simplifies the algorithm? Commit to yes or no.

Concept: Add sentinel bars and carefully handle empty stack cases to simplify code and avoid bugs.

Add a bar of height 0 at the end of the histogram to force popping all bars. This avoids separate cleanup loops. Also, handle empty stack by considering width as current index. These small tricks make the code cleaner and less error-prone.

Result

Code is simpler, less buggy, and handles all cases smoothly.

Small code tricks improve robustness and maintainability in production.

Under the Hood

The stack stores indices of bars in increasing height order. When a shorter bar appears, it means the previous taller bars cannot extend further to the right. Popping these bars lets us calculate the largest rectangle with each popped bar as the smallest height. The width is determined by the current index and the new top of the stack, which marks the left boundary. This process ensures each bar is pushed and popped once, making it efficient.

Why designed this way?

The stack approach was designed to reduce the naive O(n²) solution to O(n). It leverages the idea that the largest rectangle for a bar is bounded by the nearest smaller bars on both sides. Alternatives like brute force or segment trees are slower or more complex. The stack method balances simplicity and speed.

Input histogram: heights = [2,1,5,6,2,3]

Stack process:

Index: 0 1 2 3 4 5
Height:2 1 5 6 2 3

Start: stack empty
Push 0: [0]
Push 1 (height 1 < 2): pop 0, area=2*1=2
Stack empty, push 1: [1]
Push 2: [1,2]
Push 3: [1,2,3]
Push 4 (height 2 < 6): pop 3, area=6*1=6
Pop 2, area=5*2=10
Push 4: [1,4]
Push 5: [1,4,5]
End: pop 5, area=3*1=3
Pop 4, area=2*4=8
Pop 1, area=1*6=6

Max area = 10

Myth Busters - 4 Common Misconceptions

Quick: Do you think the largest rectangle must always include the tallest bar? Commit to yes or no.

Common Belief: The largest rectangle always includes the tallest bar in the histogram.

Reality: The largest rectangle can be formed by shorter bars spanning a wider width, not necessarily including the tallest bar.

Why it matters: Assuming the tallest bar is always part of the largest rectangle can lead to wrong answers and inefficient checks.

Quick: Do you think scanning all pairs of bars is the only way to find the largest rectangle? Commit to yes or no.

Common Belief: You must check every pair of bars to find the largest rectangle area.

Reality: Using a stack, you can find the largest rectangle in one pass without checking all pairs.

Why it matters: Believing brute force is necessary leads to slow solutions that don't scale.

Quick: Do you think the stack must store bar heights instead of indices? Commit to yes or no.

Common Belief: The stack should store the heights of bars directly.

Reality: The stack stores indices to calculate widths easily using positions, not just heights.

Why it matters: Storing heights alone makes it impossible to find the width of rectangles correctly.

Quick: Do you think the algorithm fails if bars have the same height? Commit to yes or no.

Common Belief: The stack algorithm cannot handle bars with equal heights correctly.

Reality: The algorithm handles equal heights by popping bars with height greater or equal, ensuring correct boundaries.

Why it matters: Misunderstanding this causes bugs when histograms have repeated heights.

Expert Zone

1

The stack algorithm implicitly finds both left and right boundaries in one pass, avoiding extra arrays.

2

Adding a sentinel zero-height bar at the end simplifies boundary conditions and ensures all bars are processed.

3

When popping bars, the width calculation depends on whether the stack is empty, which marks the left boundary as -1.

When NOT to use

This stack method is not suitable if bars have variable widths or if you need to find rectangles with gaps. For such cases, segment trees or divide-and-conquer approaches are better.

Production Patterns

In production, this algorithm is used in image processing to find largest rectangular areas, in financial analysis for stock span problems, and in land area calculations where histograms represent elevation profiles.

Connections

Monotonic Stack

Builds-on

Understanding this problem deepens knowledge of monotonic stacks, a pattern used to solve many range boundary problems efficiently.

Dynamic Programming

Alternative approach

While dynamic programming can solve largest rectangle problems, the stack method is often faster and uses less memory.

Real Estate Land Plotting

Application

Finding the largest rectangle in a histogram is similar to finding the largest rectangular land plot in a city skyline, showing how algorithms connect to urban planning.

Common Pitfalls

#1 Not popping all taller bars when a shorter bar appears.

Wrong approach:

for (int i = 0; i < n; i++) {
while (!stack.empty() && heights[i] < heights[stack.top()]) {
// missing pop here
}
stack.push(i);
}

Correct approach:

for (int i = 0; i < n; i++) {
while (!stack.empty() && heights[i] < heights[stack.top()]) {
int top = stack.top(); stack.pop();
int width = stack.empty() ? i : i - stack.top() - 1;
int area = heights[top] * width;
max_area = max(max_area, area);
}
stack.push(i);
}

Root cause:

Not popping means you don't calculate areas for bars that can't extend further, missing max rectangles.

#2 Using bar heights instead of indices in the stack.

Wrong approach:

stack.push(heights[i]); // pushing height directly

Correct approach:

stack.push(i); // pushing index to calculate width

Root cause:

Without indices, you cannot find the width of rectangles, so area calculation is incorrect.

#3 Forgetting to process remaining bars after iteration.

Wrong approach:

for (int i = 0; i < n; i++) { /* process */ }
// no code to pop remaining bars

Correct approach:

for (int i = 0; i <= n; i++) { /* process including sentinel */ }
while (!stack.empty()) {
int top = stack.top(); stack.pop();
int width = stack.empty() ? n : n - stack.top() - 1;
int area = heights[top] * width;
max_area = max(max_area, area);
}

Root cause:

Remaining bars might form largest rectangles extending to the end; missing them loses max area.

Key Takeaways

The largest rectangle in a histogram can be found efficiently using a stack to track increasing bar heights.

The stack helps find the nearest smaller bars on the left and right, which define rectangle boundaries.

Calculating area for each popped bar using its height and width between boundaries finds the max rectangle.

Adding a sentinel bar simplifies the algorithm by ensuring all bars are processed.

Understanding this stack method unlocks many other range and boundary problems in algorithms.

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