Largest Rectangle in Histogram

The problem description can be found in LeetCode.

Approach

This is a classic problem that can be solved by checking all the possible areas between each pair of the input array. This would require $O(n^2)$ time and $O(1)$ space.

For these kind of problems, usually, we can drop the time to $O(n)$ by using a data structure, which can store some intermediate results. In particular, for this problem, we could use a Monotonic Stack.

Let's take a look at some examples:

|     |
|  |  |
2  1  2

In the case above, the first element 2 is bounded to the second element 1. In fact, the maximum height we can obtain from the two is the minimum one. We can include the 2 in the area calculation, but the height would be 1. So, we just need to keep the base from 2 (index 0) and consider the height of 1 (index 1).

Then, once we reach the 2, we can calculate the area by having a base as 3 (2-index - 0-index + 1) and a height as 1.

An edge case would be something like:

|  |  |
|  |  |
2  2  2

This is not a monotonic increase sequence. However, we could insert a fake height of 0 in the end to consume all possible heights that are in the stack:

|  |  |
|  |  |
2  2  2  0

Solution

from itertools import chain
from typing import List, Tuple


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ans = 0
        stack: List[Tuple[int, int]] = []

        for i, height in enumerate(chain(heights, [0])):
            start = i
            while stack and stack[-1][1] > height:
                curr_i, curr_height = stack.pop()
                ans = max(ans, curr_height * (i - curr_i))
                start = curr_i

            stack.append((start, height))

        return ans

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the heights list.