Largest Rectangle In Histogram

From LeetCode:

Given an array of non-negative integers which represent histogram bar heights, find the area of largest rectangle.

Input: [2, 1, 5, 6, 2, 3]
"""
      #
    # #
    # #
    # #   #
#   # # # #
# # # # # #
0 1 2 3 4 5
"""
Output: 10

Preliminary Considerations

When determining the area occupied by any rectangle, we have two variables to consider: its width and its height.

One of the first things we can be certain about is that the largest rectangle in the graph must use the full height of one of the bars in the graph. For example, if we were given:

"""
#   # #   #
#   # #   #
# # # # # #
# # # # # # 
0 1 2 3 4 5
"""

It cannot be the case that the largest rectangle uses a height of 1 or a height of 3 –– we can always extend whatever rectangle we’re attempting to form with these values by assuming the full height of one of the bars.

With this knowledge, a naive solution becomes clear. We’ll consider every bar as a rectangle of its own and we’ll see how far left and right we can extend its area. Note that we’re not constructing a palindrome, so we’re able to move in each direction independently:

def get_largest_rectangle_area(heights):
    n = len(heights)

    def expand(m):
        nonlocal n 
        l = r = m
        # See how far left we can extend
        while l-1 >= 0 and heights[l-1] >= heights[m]:
            l -= 1
        # See how far right we can extend
        while r+1 <= n-1 and heights[r+1] >= heights[m]:
            r += 1
        return l, r        

    largest_area = 0
    for i in range(len(heights)):
        l, r = expand(i)
        largest_area = max(
            largest_area,
            heights[i] * (r - l + 1)
        )

    return largest_area

This solution gives us a time complexity of O(n^2), which is alright, but we can do much better. Let’s trade some space for a faster runtime.

Maintaining a Stack of Active Bars

It turns out that we can find the amount of space occupied by each bar more efficiently by maintaining a stack of bars of increasing height as we move from left to right.

The mental model we’ll adopt for this approach isn’t terribly different from our previous idea of “expanding” from individual bars. We’ll call each bar in the stack an active bar. Let’s go through an example:

"""
    #
  # #
  # # # 
# # # # #
0 1 2 3 4
"""

At the beginning, our stack is empty, so we simply add 0 (the index of the first bar) to our stack. When we encounter the next couple of bars, which are both taller, we append their indices too. This gives us a stack of bars of increasing height: [0, 1, 2].

"""
    #
  # #
  # # # 
# # # # #
0 1 2 3 4 
      ^
""" 
active = [0, 1, 2]

The next bar at index 3 is shorter than the topmost item in our stack (index 2), so we’ll pop off 3 and begin to compute its occupied area. Our stack is now [0, 1]. It might not obvious at this point, but we already have two pieces of critical information: s

• We know that the height of bar 2 extends rightward till index 3, since the bar 3 is shorter.
• We also know that height of bar 2 extends leftward till index 1 –– because the invariant imposed on our stack is that the bars must be of increasing height. You can say that the stack allows us to track the left bound of the current bar we’ve evaluating. s

At this point, we have what we need to determine the width of the largest rectangle extending from bar 2! The height of the bar 2 starts after 1 and ends before 3, so the width of its maximal rectangle is 1.

Let’s go through one more iteration. At this point, our stack is still [0, 1].

"""
    #
  # #
  # # # 
# # # # #
0 1 2 3 4
      ^
""" 
active = [0, 1]

Bar 3 is still shorter than bar 1, so we pop it off the stack and make similar conclusions: The height of bar 1 starts after index 0 and ends before 3, so the width of its maximal rectangle is 2.

The stack is now [0]. Since bar 3 is taller than bar 0, we append it. The same process continues until we reach the end of the histogram.

From Intuition To Code

The only hurdle left is to convert the approach described above into code:

def get_largest_rectangle_area(heights):

    active = []
    largest_area = 0

    for i, new_height in enumerate(heights + [0]):
        while active and heights[active[-1]] >= new_height:
            popped_idx = active.pop()

            # Compute height
            height = heights[popped_idx]

            # Compute width
            leftbound = active[-1] if active else -1
            rightbound = i   
            width = rightbound - leftbound - 1

            # Update result
            largest_area = max(largest_area, width * height)
            
        active.append(i)

    return largest_area

For this particular problem, translating your approach into code might be less intuitive than usual. You’re likely to think about building up your stack first before flushing it, because that’s the easier way to reason about the algorithm. The code above, however, is written the other way around. The key here is to remember that, as you’re live coding, your algorithm doesn’t always have to fleshed out from top to bottom –– sometimes, subsequent steps in loops involve operations which have to be defined above your current set of instructions.

On a separate note, notice that we need some way to guarantee that our stack of active bars is emptied once we reach the end of the main loop. To tackle this, our code extends the heights parameter with an extra [-1] so that we can force a right bound on any active bars and eject them from the stack.

Given n heights, our algorithm runs in O(n) space and O(n) time.

With that, we’ve solved the Largest Rectangle In Histogram problem 📊📊.

Full Solution

def get_largest_rectangle_area(heights):

    active = []
    largest_area = 0

    for i, new_height in enumerate(heights + [0]):
        while active and heights[active[-1]] >= new_height:
            popped_idx = active.pop()

            height = heights[popped_idx]

            leftbound = active[-1] if active else -1
            rightbound = i   
            width = rightbound - leftbound - 1

            largest_area = max(largest_area, width * height)
            
        active.append(i)

    return largest_area