Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Largest Rectangle in a Histogram by PythonLearner
from typing import List, Iterable
from itertools import groupby, chain
def rectangle_areas(histogram: List[int], height: int) -> Iterable[int]:
widths = (len(list(group)) for key, group in groupby(histogram, lambda column: column >= height) if key)
return (height*width for width in widths)
def largest_histogram(histogram: List[int]) -> int:
heights = set(histogram)
areas = chain.from_iterable(rectangle_areas(histogram, height) for height in heights)
return max(areas)
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert largest_histogram([5]) == 5, "one is always the biggest"
assert largest_histogram([5, 3]) == 6, "two are smallest X 2"
assert largest_histogram([1, 1, 4, 1]) == 4, "vertical"
assert largest_histogram([1, 1, 3, 1]) == 4, "horizontal"
assert largest_histogram([2, 1, 4, 5, 1, 3, 3]) == 8, "complex"
print("Done! Go check it!")
Feb. 24, 2019
