Problem Statement in English

You’re given an array of integers heights representing the histogram’s bar height where the width of each bar is 1. Return the area of the largest rectangle in the histogram.

Approach

Something we need to realise is that once a a taller bar encounters a shorter bar, the taller bar can no longer extend to the right. This is because the area of the rectangle is limited by the height of the shorter bar.

And so, we can calculate the area of the rectangle formed by the taller bar immediately as its max width is upto and excluding the shorter bar. Further, the shorter can be thought of as starting at the index of the taller bar, since it can extend upto the current index all teh way from wherever the taller bar started.

So we’re going to use a monotonic stack to keep track of the bars in increasing order. When we encounter a shorter bar, we pop the taller bars from the stack and calculate their area on the spot. We also keep track of the earliest index that the popped bar can extend to, which is the index of the shorter bar we just encountered. Then we push the shorter bar onto the stack with the earliest index it can extend to.

Finally, after we’ve processed all bars, we need to pop any remaining bars in the stack and calculate their area as well, since they can extend to the end of the histogram.

And we’re done!

Solution in Python


class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []
        res = 0

        for i, v in enumerate(heights):
            earliest = i
            while stack and stack[-1][1] > v:
                earliest, value = stack.pop()
                res = max(res, (i - earliest) * value)
            stack.append((earliest, v))
            pass

        N = len(heights)
        for index, height in stack:
            res = max(res, (N - index) * height)

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the heights array once and each bar is pushed and popped from the stack at most once, the time complexity is linear with respect to the number of bars.

  • Space: $O(n)$
    Since we are using a stack to keep track of the bars, the space complexity is also linear with respect to the number of bars.

And we are done.