Largest Rectangle Area in a Histogram

Problem

Return the area of the largest rectangle that fits inside a histogram whose bar heights are given by heights with unit width.

Maintain a monotonic stack of indices with increasing heights; when a shorter bar arrives, pop each taller bar and compute its best rectangle using the new right boundary. A sentinel zero at the end flushes any remaining bars.

Hint

Popped bar height times the distance between its new left boundary and the current index gives its best width.

Test cases

case 1

in: [[2,1,5,6,2,3]]

expected: 10

case 2

in: [[2,4]]

expected: 4

case 3

in: [[]]

expected: 0

case 4

in: [[5]]

expected: 5

case 5

in: [[2,2,2]]

expected: 6

Starter codePython

def largest_rectangle_area(heights):
    # Your code here
    pass

5 test cases · run your code against them in the editor