Histogram stack algorithm in Python
Maintain a stack of increasing bar heights; each popped bar yields its maximal rectangle in O(n) total time.
- File
histogram_stack_algorithm.py, 46 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/histogram-stack-algorithm/. The authors are listed in prov/PXWH0K.jsonl.
from typing import Union
Number = Union[int, float]
def largest_rectangle(h: list[Number]) -> Number:
"""Return the largest area of a rectangle under the histogram with bar heights h.
Each bar has width 1. Precondition: every height is >= 0.
Cost: O(n) time, O(n) extra space for the stack.
"""
n = len(h)
stack: list[int] = [] # @line L1
best: Number = 0
for i in range(n + 1): # @line L2
x = h[i] if i < n else 0 # @line L3
while stack and h[stack[-1]] >= x: # @line L4
k = stack.pop() # @line L5
left = stack[-1] if stack else -1 # @line L6
best = max(best, h[k] * (i - left - 1)) # @line L7
stack.append(i) # @line L8
return best # @line L9
def largest_rectangle_span(h: list[Number]) -> tuple[Number, int, int]:
"""Return (area, a, b): a largest rectangle under h covers bars a..b (inclusive).
Returns (0, 0, -1) for an empty histogram. Same precondition and cost.
"""
n = len(h)
stack: list[int] = []
best: Number = 0
span = (0, -1)
for i in range(n + 1):
x = h[i] if i < n else 0
while stack and h[stack[-1]] >= x:
k = stack.pop()
left = stack[-1] if stack else -1
area = h[k] * (i - left - 1)
if area > best:
best, span = area, (left + 1, i - 1)
stack.append(i)
return best, span[0], span[1]
test_histogram_stack_algorithm.py 44 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/histogram-stack-algorithm/. The authors are listed in prov/PXWH0K.jsonl.
import random
from histogram_stack_algorithm import largest_rectangle, largest_rectangle_span
def brute(h: list[int]) -> int:
return max(
((j - i + 1) * min(h[i : j + 1]) for i in range(len(h)) for j in range(i, len(h))),
default=0,
)
def test_example() -> None:
assert largest_rectangle([2, 1, 5, 6, 2, 3]) == 10
assert largest_rectangle_span([2, 1, 5, 6, 2, 3]) == (10, 2, 3)
def test_edges() -> None:
assert largest_rectangle([]) == 0
assert largest_rectangle_span([]) == (0, 0, -1)
assert largest_rectangle([0]) == 0
assert largest_rectangle([7]) == 7
assert largest_rectangle([1, 2, 3]) == 4
assert largest_rectangle([1, 2, 3, 4, 5]) == 9
assert largest_rectangle([3, 3, 3]) == 9
assert largest_rectangle([2, 4]) == 4
assert largest_rectangle([0, 0, 1, 0]) == 1
assert largest_rectangle([1.5, 1.5]) == 3.0
def test_against_brute_force() -> None:
rng = random.Random(20261105)
for _ in range(3000):
n = rng.randrange(0, 20)
h = [rng.randrange(0, 7) for _ in range(n)]
expected = brute(h)
assert largest_rectangle(h) == expected
area, a, b = largest_rectangle_span(h)
assert area == expected
if area:
assert (b - a + 1) * min(h[a : b + 1]) == area
What the next level needs
- the tests did not run in this build