Largest Rectangle in Histogram

Problem Description

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.

Naive Solution

The brute force solution is to consider every possible rectangle that can be formed within the histogram. For each pair of bars i and j (where i <= j), we find the minimum height bar between these two indices. The area of the rectangle formed by these bars is then min_height * (j - i + 1). We iterate through all possible i and j pairs, calculate the area for each, and keep track of the maximum area found so far.

Code

def largestRectangleArea_brute_force(heights):
    max_area = 0
    n = len(heights)
    for i in range(n):
        for j in range(i, n):
            min_height = min(heights[i:j+1])
            max_area = max(max_area, min_height * (j - i + 1))
    return max_area

Time Complexity

The outer loop runs n times, and the inner loop also runs approximately n times. The min operation within the inner loop takes O(n) in the worst case. Therefore, the overall time complexity is O(n^3).

Space Complexity

The space complexity is O(1) as we use only a constant amount of extra space.

Optimal Solution

A more efficient solution utilizes a stack. The idea is to maintain a stack of increasing bar indices. When we encounter a bar that is shorter than the bar at the top of the stack, it means we've found the right boundary for the rectangle formed by the bar at the top of the stack. We pop the top of the stack and calculate the area of the rectangle. The width of this rectangle is determined by the current index and the index of the bar before the popped bar in the stack.

Algorithm

1. Initialize an empty stack.
2. Iterate through the heights array.
3. While the stack is not empty and the current bar is shorter than the bar at the top of the stack:
   • Pop the top of the stack.
   • Calculate the area of the rectangle formed by the popped bar.
   • Update the maximum area if necessary.
4. Push the current bar's index onto the stack.
5. After iterating through all bars, if the stack is not empty, repeat step 3 until the stack is empty.

Edge Cases

• Empty histogram: return 0.
• Histogram with one bar: return the height of the bar.
• Histogram with increasing bars: need to clear the stack at the end.
• Histogram with decreasing bars: handled correctly by the stack.

Code

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    n = len(heights)
    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack:
        height = heights[stack.pop()]
        width = n if not stack else n - stack[-1] - 1
        max_area = max(max_area, height * width)

    return max_area

Time Complexity

The time complexity is O(n), where n is the number of bars. Each bar is pushed onto the stack and popped from the stack at most once.

Space Complexity

The space complexity is O(n) in the worst-case scenario, such as when the histogram bars are in increasing order, and all indices are stored in the stack.