Largest Rectangle in Histogram Using Stack in DSA C++ - Build from Scratch

Largest Rectangle in Histogram Using Stack

📖 Scenario: You are working with a histogram that shows the heights of bars side by side. Each bar has a width of 1 unit. You want to find the largest rectangle that can fit inside this histogram.Imagine you have a row of books of different heights on a shelf. You want to find the biggest flat area you can cover by stacking some books next to each other without gaps.

🎯 Goal: Build a program that uses a stack to find the largest rectangle area in a histogram represented by a list of bar heights.

📋 What You'll Learn

Create a vector called heights with the exact values: 2, 1, 5, 6, 2, 3

Create an integer variable called max_area and set it to 0

Use a stack of integers called index_stack to help find the largest rectangle

Implement the logic to calculate the largest rectangle area using the stack

Print the max_area as the final output

💡 Why This Matters

🌍 Real World

Finding the largest rectangle in a histogram is useful in image processing, stock market analysis, and layout design where you need to find the biggest continuous area.

💼 Career

This algorithm is a common interview question and helps develop skills in using stacks and understanding efficient area calculations.

1

Create the histogram data

Create a vector<int> called heights with these exact values: 2, 1, 5, 6, 2, 3

DSA C++

#include 
#include 
#include 

int main() {
    // Create the vector heights with values 2, 1, 5, 6, 2, 3
    // Your code here
}

Hint

Use std::vector<int> heights = {2, 1, 5, 6, 2, 3}; to create the histogram heights.

2

Initialize the maximum area variable

Create an integer variable called max_area and set it to 0

DSA C++

#include 
#include 
#include 

int main() {
    std::vector heights = {2, 1, 5, 6, 2, 3};
    // Create max_area and set to 0
    // Your code here
}

Hint

Use int max_area = 0; to start tracking the largest rectangle area.

3

Use a stack to find the largest rectangle area

Create a stack<int> called index_stack. Use a for loop with variable i from 0 to heights.size(). Inside the loop, while index_stack is not empty and heights[i] is less than heights[index_stack.top()], pop from index_stack, calculate area with the popped height and update max_area. After the while loop, push i onto index_stack. After the loop, while index_stack is not empty, pop and calculate area similarly to update max_area.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector heights = {2, 1, 5, 6, 2, 3};
    int max_area = 0;
    // Create stack index_stack
    // Use for loop with i from 0 to heights.size()
    // Inside loop, use while loop to pop from stack and calculate area
    // Push i to stack
    // After loop, pop remaining stack and calculate area
    // Your code here
}

Hint

Use a stack to keep indexes of bars. Pop when current height is less than top of stack height. Calculate area using popped height and width between current index and new top of stack.

4

Print the largest rectangle area

Print the value of max_area using std::cout

DSA C++

#include 
#include 
#include 

int main() {
    std::vector heights = {2, 1, 5, 6, 2, 3};
    int max_area = 0;
    std::stack index_stack;
    int n = heights.size();
    for (int i = 0; i  max_area) {
                max_area = area;
            }
        }
        index_stack.push(i);
    }
    while (!index_stack.empty()) {
        int height = heights[index_stack.top()];
        index_stack.pop();
        int width = index_stack.empty() ? n : n - index_stack.top() - 1;
        int area = height * width;
        if (area > max_area) {
            max_area = area;
        }
    }
    // Print max_area
    // Your code here
}

Hint

Use std::cout << max_area << std::endl; to print the largest rectangle area.

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