HardStacks QueuesAI interview only
Largest Rectangle in Histogram
Asked atgoogleamazonmetamicrosoftapplebloombergadobeuber
01 · Problem
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
02 · Examples
Example 01
Input
heights = [2,1,5,6,2,3]
Output
10
The largest rectangle is formed by bars at indices 2 and 3 (heights 5 and 6), giving area = 5 * 2 = 10.
Example 02
Input
heights = [2,4]
Output
4
The single bar at index 1 with height 4 forms the largest rectangle with area = 4 * 1 = 4.
Example 03
Input
heights = [2,1,2]
Output
3
The rectangle spanning all three bars with height 1 gives area = 1 * 3 = 3, which is the largest.
03 · Constraints
- 011 <= heights.length <= 105
- 020 <= heights[i] <= 104
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.