Problem overview
The function largestRectangleArea receives a slice heights, where each value is the height of one bar in a histogram and every bar is 1 unit wide. It returns the area of the largest rectangle that fits inside the bars. The rectangle's sides run along the bar edges, so it spans a run of neighboring bars and its height is limited by the shortest bar in that run.
For heights = [2, 1, 5, 6, 2, 3] the answer is 10: the bars of height 5 and 6 side by side form a rectangle of height 5 and width 2. For [2, 4] the answer is 4, either the 4-high bar alone or a 2-high rectangle across both bars. The input holds up to 100,000 bars, each between 0 and 10,000 high, so an O(n²) search over every pair of bars is too slow.
Approach: for each bar, how far can it stretch?
Any rectangle is limited by its lowest bar. So it is enough to try each bar i as that lowest bar and ask how wide a rectangle of height heights[i] can be. It can extend left and right as long as the neighboring bars are at least as tall as bar i. It stops at the first bar that is lower on each side.
So for each i we need two numbers: left[i], the index of the nearest lower bar on the left, and right[i], the index of the nearest lower bar on the right. Both of those bars are excluded from the rectangle, so its width is right[i] - left[i] - 1 and its area is heights[i] * (right[i] - left[i] - 1). The answer is the maximum of that over all bars.
When there is no lower bar, the code pretends a bar of height 0 stands just outside the histogram: index -1 on the left and index n on the right.
Finding those nearest lower bars quickly is what a monotonic stack is for. Scan the bars from left to right and keep a stack of indices whose bars are still waiting for a lower bar to their right. Their heights never decrease from bottom to top. When a new bar i arrives, every bar on top of the stack that is taller than it has just met its first lower bar on the right: pop it and record i. Then push i. A second scan from right to left, with the same logic, finds the lower bars on the left.
For [2, 1, 5, 6, 2, 3] the two scans produce:
right = [1 6 4 4 6 6]
left = [-1 -1 1 2 1 4]
The areas per bar are 2, 6, 10, 6, 8 and 3, so the largest is 10, from the bar of height 5, which stretches from index 2 to index 3.
Step by step
- Store the length in
n, since it is used many times. - Create
leftwithmake([]int, n). It will hold the nearest lower bar on the left for each index. - Create
rightthe same way. - Loop over the indices to give both slices their starting values, since
makefills them with zeros. - Set
left[i] = -1: until a lower bar is found, the imaginary 0-high bar before the first index is the limit. - Set
right[i] = n: likewise, the imaginary bar just past the last index.ncan't be mistaken for a real index. - Create the stack
stas an empty[]int. Its top is the last element. - Scan left to right.
- Call the helper
removeAndUpdate(heights, &st, right, i). Passingrightmeans the lower bars it finds are recorded as right neighbors. - Reset the stack to a new empty slice. Whatever stayed on it has no lower bar to the right, and its
rightvalue is stilln. - Scan right to left with
ifromn - 1down to 0. - Call the same helper with
left. The helper doesn't care about direction, so it now finds left neighbors. - Start
answerat 0. - Loop over the bars again and try each as the limiting height.
- Update the answer with
max(answer, heights[i]*(right[i]-left[i]-1)). - Return
answer. - Write the helper
removeAndUpdate(heights []int, st *[]int, arr []int, i int), with no return value. - Pop while the top is taller. The loop runs while the stack is not empty and
heights[i]is less than the height of the bar whose index is on top. - Record the neighbor. Bar
iis the first lower bar the popped index has met, soarrat that index becomesi. - Pop it by shortening the stack by one element.
- Push
i. Every taller bar is gone, so the heights on the stack still never decrease. Bars exactly as tall as baristay, because only strictly taller ones are popped.
The solution in Go
func removeAndUpdate(heights []int, st *[]int, arr []int, i int) {
for len(*st) > 0 && heights[i] < heights[(*st)[len(*st)-1]] {
arr[(*st)[len(*st)-1]] = i
*st = (*st)[:len(*st)-1]
}
*st = append(*st, i)
}
func largestRectangleArea(heights []int) int {
n := len(heights)
left := make([]int, n)
right := make([]int, n)
for i := 0; i < n; i++ {
left[i] = -1
right[i] = n
}
st := []int{}
for i := 0; i < n; i++ {
removeAndUpdate(heights, &st, right, i)
}
st = []int{}
for i := n - 1; i >= 0; i-- {
removeAndUpdate(heights, &st, left, i)
}
answer := 0
for i := 0; i < n; i++ {
answer = max(answer, heights[i]*(right[i]-left[i]-1))
}
return answer
}
The Go details worth knowing:
- Why
stis a pointer. A slice is a small value holding a pointer to its data, a length and a capacity. Passing it by value gives the helper a copy of those three fields. Popping with[:len-1]or pushing withappendwould change only the copy, so the helper takes*[]intand works through*st:
stack := []int{4, 7, 9}
p := &stack
*p = (*p)[:len(*p)-1]
fmt.Println(stack, (*p)[len(*p)-1]) // [4 7] 7
(*st)[...]needs parentheses. Indexing binds tighter than*, so*st[0]would mean "dereferencest[0]", which doesn't compile for a pointer to a slice.(*st)[0]first takes the slice, then indexes it.- Why
arris not a pointer. The helper only writes into existing elements, and the caller's slice shares those elements with the copy. Assigningarr[k] = iis visible to the caller. A slice would need a pointer only if the helper changed its length. - Short-circuit order. In
len(*st) > 0 && heights[i] < ..., the length check comes first and stops the evaluation when the stack is empty, so the top is never read from an empty stack. - Built-in
max. Since Go 1.21,minandmaxare built-in functions that work on ordered types, includingint, so no import is needed. make([]int, n)givesnzeros. That is why the first loop sets every entry explicitly.
Complexity
Time: O(n). In each of the two scans, every index is pushed once and popped at most once. The inner for loop looks like it could make things quadratic, but its pops are bounded by the pushes, so each scan does O(n) work in total. The last loop is one more pass.
Space: O(n). The left and right slices hold n values each, and the stack can hold up to n indices, for example when the heights only increase.
Edge cases and common mistakes
- A single bar.
[5]gives 5:leftis -1,rightis 1, and the width is 1. - Zero heights.
[0]gives 0, and a 0-high bar always has zero area, but it still splits the histogram, since no rectangle can cross it. - Equal bars.
[3, 3, 3]gives 9. The loop pops only strictly taller bars, so equal bars stay on the stack and each of them stretches across the whole histogram, from -1 to 3. - Increasing heights.
[1, 2, 3, 4, 5]gives 9, from the bar of height 3 with width 3. Nothing is popped in the first scan, sorightstaysnfor every index. - Off-by-one in the width. The bars at
left[i]andright[i]are lower, so they are outside the rectangle. The width isright[i] - left[i] - 1, notright[i] - left[i]. - Popping with
<=. That would also pop equal bars, so each bar's neighbor could be an equal bar instead of a lower one. For[3, 3, 3]every width shrinks to 1 and the function would return 3 instead of 9. - Overflow. The largest possible area is 10,000 times 100,000, which is a billion, well inside a 64-bit
int.
Testing
[2, 1, 5, 6, 2, 3]gives 10.[2, 4]gives 4.[5]gives 5.[0]gives 0.[3, 3, 3]gives 9.[1, 2, 3, 4, 5]gives 9.
