Problem Statement

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.

Additional information

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

Example 1:

Input: heights = [2, 1, 5, 6, 2, 3]

Output: 10

Explanation: The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2, 4]

Output: 4

Brute Force

Intuition
For each bar in the histogram, let's assume it is the shortest bar in the potential rectangle. We then expand to the left and right as far as possible while keeping the height greater than or equal to the current bar's height. The width is the distance between the left and right boundaries, and the area is height * width. We calculate this for every bar and find the maximum.

Algorithm

1. Initialize max_area = 0.
2. Iterate i from 0 to n-1.
3. Set min_height = infinity.
4. Iterate j backwards from i to 0.

• Update min_height = min(min_height, heights[j]).
• Calculate width = i - j + 1.
• Update max_area = max(max_area, min_height * width).

5. Return max_area.

def largest_rectangle_area(heights: list[int]) -> int:
    max_area = 0
    n = len(heights)
    
    for i in range(n):
        min_h = float('inf')
        for j in range(i, -1, -1):
            min_h = min(min_h, heights[j])
            width = i - j + 1
            max_area = max(max_area, min_h * width)
            
    return max_area

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: Nested loops check every possible sub-array ending at i.

• Space complexity: O(1)

• Reason: Constant extra space.

Monotonic Stack (Optimal)

Intuition
To improve efficiency, we need to find the Next Smaller Element to the left and right for every bar in average time.
A Monotonic Increasing Stack is perfect for this. We store indices in the stack such that their corresponding heights are always increasing.

• When we encounter a current bar heights[i] that is smaller than the bar at the top of the stack (heights[stack[-1]]), it means the rectangle formed by stack[-1] cannot extend any further to the right. The current index i is the Right Boundary.
• The Left Boundary is the element just below it in the stack (since the stack is increasing).
• We pop the top element, calculate its max area, and repeat until the stack property (increasing heights) is restored.

Algorithm

1. Append a 0 to the end of heights. This ensures that any remaining bars in the stack are processed at the end.
2. Initialize an empty stack with -1 (acting as a dummy left boundary).
3. Initialize max_area = 0.
4. Iterate i through the heights array:

• While the stack is non-empty (has more than just -1) and heights[stack[-1]] >= heights[i]:

• Pop the top index: h_index = stack.pop().

• The height of the rectangle is h = heights[h_index].

• The width is determined by the current index i (right boundary) and the new top of the stack stack[-1] (left boundary): w = i - stack[-1] - 1.

• Update max_area = max(max_area, h * w).

• Push i onto the stack.

5. Return max_area.

def largest_rectangle_area(heights: list[int]) -> int:
    heights.append(0)  # Append 0 to flush stack at the end
    stack = [-1]
    max_area = 0
    
    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
        
    return max_area

Time & Space Complexity

• Time complexity: O(n)

• Reason: Each element is pushed onto the stack once and popped once.

• Space complexity: O(n)

• Reason: The stack can grow to size n in the worst case (strictly increasing heights).