Given an array of integers representing the heights of bars in a histogram where each bar has width 1, explain how you would find the area of the largest rectangle that can be formed within the histogram.
For example:
Input: [2, 1, 5, 6, 2, 3] Output: 10
Explanation: The largest rectangle has height 5 and width 2 (bars at indices 2 and 3), giving area 5 * 2 = 10.
A brute force approach would be O(n^2). Can you do better?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
For each bar, the maximum rectangle using that bar's height extends left and right as far as all bars are at least that height. The challenge is efficiently finding those boundaries.
- Hint 2
Consider using a stack that maintains bars in increasing height order. When you encounter a shorter bar, the taller bars on the stack can no longer extend further right.
- Hint 3
When popping a bar from the stack, its right boundary is the current index and its left boundary is the new stack top. Calculate width as current_index minus stack_top minus 1.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.