Largest Rectangle in Histogram Using Stack in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a stack to find the largest rectangle in a histogram?

Use a stack to keep track of bars in increasing height order. When a smaller bar appears, calculate areas with bars popped from the stack as the smallest bar, ensuring all rectangles are considered.

beginner

Why do we push the index of bars onto the stack instead of their heights?

Storing indices allows us to calculate the width of rectangles easily by subtracting indices, which is needed to find the area of rectangles.

intermediate

What triggers the calculation of rectangle areas when using the stack method?

When the current bar height is less than the height of the bar at the top of the stack, we pop from the stack and calculate the area with the popped bar as the smallest height.

intermediate

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

Width = current index - index of new top of stack - 1. If stack is empty after popping, width = current index.

beginner

What is the time complexity of the largest rectangle in histogram algorithm using a stack?

O(n), because each bar is pushed and popped at most once from the stack.

What data structure is used to solve the largest rectangle in histogram problem efficiently?

A Stack

B Queue

C Linked List

D Hash Map

A stack is used to keep track of bars in increasing order to calculate areas efficiently.

When do we pop bars from the stack during the algorithm?

A When the current bar is taller than the top of the stack

B When the stack is empty

C At the end of the array only

D When the current bar is shorter than the top of the stack

We pop bars when the current bar is shorter to calculate areas with the popped bars as the smallest height.

What does the width of the rectangle depend on when popping from the stack?

A The height of the current bar

B The difference between current index and new top of stack index minus one

C The total number of bars

D The difference between current index and popped index

Width is calculated as current index minus the index of the new top of the stack minus one.

What is the maximum number of times a bar can be pushed or popped from the stack?

A Once

B Twice

C Multiple times

D Never

Each bar is pushed and popped at most once, ensuring O(n) time complexity.

What is the final step after processing all bars in the histogram?

A Return the maximum height

B Clear the stack without calculation

C Pop remaining bars from the stack and calculate areas

D Add all bar heights

After processing all bars, pop remaining bars to calculate areas for rectangles extending to the end.

Explain step-by-step how the stack helps find the largest rectangle in a histogram.

Think about how the stack keeps track of bars and when areas are calculated.

Describe how to calculate the width of a rectangle when popping a bar from the stack.

Width depends on indices around the popped bar.

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