Largest Rectangle in Histogram

Find the maximum area rectangle that can be formed from consecutive bars.

histogram stack maximum-area array

You are given a list of non-negative integers `heights`, where each element represents the height of a bar in a histogram. The width of each bar is 1. Write a function `largest_rectangle_area(heights)` that returns the area of the largest rectangle that can be formed entirely within the histogram. A rectangle is formed by choosing a contiguous segment of bars and using the minimum height in that segment as the rectangle's height; its area is that minimum height multiplied by the number of bars in the segment. For example, with heights `[2,1,5,6,2,3]`, the largest rectangle has area 10 (using bars at indices 2 and 3, each of height 5 and 6, with min height 5 and width 2). The function should return an integer. You may assume `heights` is a list of non-negative integers and can be empty (in which case return 0).

Constraints

0 <= len(heights) <= 10^5; 0 <= heights[i] <= 10^4. Time complexity should be O(n), where n is the number of bars. Space complexity O(n) in the worst case.

Example

>>> largest_rectangle_area([2,1,5,6,2,3])
10
>>> largest_rectangle_area([2,4])
4
>>> largest_rectangle_area([1])
1
>>> largest_rectangle_area([])
0

40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about each bar as the shortest bar in a rectangle that extends left and right until a smaller bar is encountered.

Use a stack to maintain indices of bars in increasing height order. When a smaller height is found, you can compute areas for bars popped from the stack.

After processing all bars, pop remaining indices from the stack to compute areas for rectangles that extend to the end.

Remember to handle duplicate heights correctly by using strict comparison when popping.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.