Largest Rectangle in Histogram
HardThe problem
Each number in the list is the height of a bar in a bar chart, and every bar is 1 unit wide, standing side by side. Return the area of the biggest rectangle you can draw that fits fully inside the bars (it must cover whole bars next to each other).
- Example 1Input: heights = [3, 1, 3, 2, 2]Output: 6
The last three bars (3, 2, 2) can hold a rectangle of height 2 and width 3: area 6. Using all 5 bars only allows height 1: area 5.
- Example 2Input: heights = [4]Output: 4
One bar: 4 × 1.
- 1 ≤ heights.length ≤ 100,000
- 0 ≤ heights[i] ≤ 10,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
For each bar, how far left and right can its height extend? Both limits are "the first shorter bar".
The idea
Monotonic increasing stack of (start index, height). When a shorter bar arrives, pop taller bars, computing their area with the width they covered; the new bar inherits the earliest popped start.
Target: O(n) time, O(n) space
Go function shape
func largestRectangleArea(heights []int) intReference solution
Tested with go test. Try it yourself first, then compare.
// LargestRectangleArea: largest rectangle inside a histogram.
// Stack of increasing heights. A shorter bar pops taller ones; each popped bar's
// rectangle extends left to the new stack top and right to the current index.
func LargestRectangleArea(heights []int) int {
best := 0
stack := []int{} // indices with increasing heights
for i := 0; i <= len(heights); i++ {
h := 0 // sentinel bar of height 0 flushes the stack at the end
if i < len(heights) {
h = heights[i]
}
for len(stack) > 0 && heights[stack[len(stack)-1]] >= h {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
left := -1
if len(stack) > 0 {
left = stack[len(stack)-1]
}
best = max(best, height*(i-left-1))
}
stack = append(stack, i)
}
return best
}