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 until the stack is in order again.

beginner

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

Storing indices helps calculate the width of rectangles easily by subtracting indices when popping bars from the stack.

intermediate

What happens when we encounter a bar shorter than the bar at the top of the stack?

We pop bars from the stack and calculate the area for each popped bar using its height and the width determined by current index and the new top of the stack.

intermediate

How do we handle remaining bars in the stack after processing all histogram bars?

Pop all remaining bars and calculate area for each using the total histogram length as the right boundary.

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 Array

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

When do we calculate the area of a rectangle in the stack-based approach?

A When a shorter bar is found

B At the end only

C When a taller bar is found

D Before pushing any bar

We calculate area when we find a bar shorter than the top of the stack, popping taller bars.

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

A Current index minus popped bar's index

B Difference between current index and new top of stack index minus one

C Height of the popped bar

D Number of bars in the histogram

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

What is pushed onto the stack during the algorithm?

A Bar heights

B Area values

C Bar heights and indices

D Bar indices

Indices of bars are pushed to help calculate widths later.

What is the overall time complexity of the stack-based largest rectangle algorithm?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

Each bar is pushed and popped once, so the time complexity is linear O(n).

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 the rectangle when popping a bar from the stack.

Remember the stack stores indices, not heights.