Largest Rectangle in Histogram

Largest Rectangle in Histogram

This problem asks us to find the largest rectangular area that can be fit within a histogram. The histogram is represented by an array of integers, where each integer represents the height of a bar and each bar has a width of 1.

Brute Force Solution

A brute-force approach would involve considering every possible rectangle within the histogram and calculating its area. We can iterate through all possible starting and ending points for the rectangle and determine the height of the rectangle based on the smallest bar within that range. The area is then calculated by multiplying the width (ending point - starting point + 1) by the minimum height. Finally, we keep track of the maximum area found so far.

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])
            width = j - i + 1
            area = min_height * width
            max_area = max(max_area, area)
    return max_area

Time Complexity: O(n^2), where n is the number of bars in the histogram. We have nested loops to consider every possible rectangle.

Space Complexity: O(1), as we only use a few variables to store the maximum area, minimum height, and width.

Optimal Solution (Using Stack)

A more efficient approach involves using a stack to keep track of the indices of increasing heights. When we encounter a bar that is shorter than the bar at the top of the stack, it indicates that we can calculate the area of a rectangle with the bar at the top of the stack as the minimum height. The width of the rectangle is determined by the distance between the current bar and the bar before the one at the top of the stack.

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    n = len(heights)
    
    for i in range(n + 1):
        # use a zero height at the end to clear the stack
        while stack and (i == n or heights[stack[-1]] >= heights[i]):
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
            
    return max_area

Explanation:

1. Initialization: We initialize an empty stack and a variable max_area to 0.
2. Iteration: We iterate through the heights array, appending a 0 to the end. This ensures that all bars in the stack are processed at the end.
3. Stack Management:
   • While the stack is not empty and the current height is less than or equal to the height at the top of the stack, we pop the top element from the stack.
   • The popped element's height is used as the height of a potential rectangle.
   • The width of the rectangle is calculated based on the current index i and the index of the previous element in the stack (if the stack is not empty).
   • The area is calculated and max_area is updated if necessary.
4. Stack Append: We append the current index to the stack.
5. Return: Finally, we return the max_area.

Time Complexity: O(n), where n is the number of bars in the histogram. Each bar is pushed onto the stack and popped off the stack at most once.

Space Complexity: O(n), as the stack can contain up to n indices in the worst case (when the heights are in increasing order).

Edge Cases

• Empty Histogram: If the input heights array is empty, the maximum area is 0.
• Histogram with One Bar: If the histogram contains only one bar, the maximum area is the height of that bar.
• Histogram with Decreasing Heights: A histogram with decreasing heights will result in multiple calculations within the while loop, correctly capturing the maximum area. For example, heights = [5,4,3,2,1]
• Histogram with Increasing Heights: A histogram with increasing heights will build up in the stack until a smaller height is reached, or the end is reached, triggering calculations.