Largest Rectangle in Histogram

December 30, 2023

Problem #

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.

Solution #

Here’s the Python code for solving the problem of finding the area of the largest rectangle in a histogram:

def largestRectangleArea(heights):
    """
    Calculate the area of the largest rectangle in the histogram.
    
    Args:
    heights (List[int]): List of integers representing the heights of the bars in the histogram.

    Returns:
    int: The area of the largest rectangle in the histogram.
    """
    stack = []
    max_area = 0
    # Append a zero height to handle remaining elements in stack at the end
    extended_heights = heights + [0]

    for i, h in enumerate(extended_heights):
        # Pop from the stack and calculate area when the current height is less than the stack's top height
        while stack and extended_heights[stack[-1]] > h:
            height = extended_heights[stack.pop()]
            # Calculate the width
            width = i if not stack else i - stack[-1] - 1
            # Update max_area
            max_area = max(max_area, height * width)
        # Push current index to stack
        stack.append(i)

    return max_area

# Example usage
heights = [2, 1, 5, 6, 2, 3]
largest_rectangle_area = largestRectangleArea(heights)
print(largest_rectangle_area)

This code defines a function largestRectangleArea that takes a list of integer heights as input. It uses a stack to efficiently calculate the largest rectangle area in a histogram, where each bar’s width is 1. The function iterates through the heights, using the stack to keep track of bars that are potential candidates for forming the largest rectangle. It calculates the area for each bar by considering the width it can extend to the left and right before encountering a shorter bar. The function returns the maximum area found.

Solution Analysis #

The provided Python code calculates the largest rectangle area in a histogram, where each bar’s width is considered to be 1 unit. Let’s break down how the code works:

1. Function Definition:

   • def largestRectangleArea(heights):
   • The function largestRectangleArea is defined to take one argument, heights, which is a list of integers representing the heights of bars in a histogram.

2. Initializing Variables:

   • stack = []: A stack is initialized to keep track of the indices of the bars.
   • max_area = 0: This variable will store the maximum area of the rectangle found so far.
   • extended_heights = heights + [0]: The heights array is extended by adding a zero at the end. This is a clever trick to ensure that any remaining bars in the stack are processed after iterating through all the heights.

3. Iterating Over Extended Heights:

   • for i, h in enumerate(extended_heights):
   • The code iterates over each bar’s height in the extended_heights array, using enumeration to get both the index (i) and the height (h) of each bar.

4. Processing the Stack:

   • while stack and extended_heights[stack[-1]] > h:
   • This loop processes bars that are on the stack as long as the current height (h) is less than the height at the top of the stack. This implies that the rectangle including the bar at the top of the stack cannot be extended further to the right.

5. Calculating Area:

   • height = extended_heights[stack.pop()]: This gets the height of the last bar added to the stack and removes it from the stack.
   • width = i if not stack else i - stack[-1] - 1: The width of the rectangle is calculated based on the current index (i) and the index of the next lower bar on the stack (if there is one).
   • max_area = max(max_area, height * width): The area of the rectangle with the current bar as the shortest bar is calculated and compared with the max_area. If it’s larger, max_area is updated.

6. Pushing Current Index to Stack:

   • stack.append(i): The current index is added to the stack. This is done after processing the stack, ensuring that the stack is either empty or contains bars of increasing heights from top to bottom.

7. Returning the Maximum Area:

   • return max_area: After iterating through all bars, the function returns the maximum rectangle area found.

8. Example Usage:

   • The code includes an example usage where it calculates the largest rectangle area for the heights [2, 1, 5, 6, 2, 3] and prints the result.

The key idea of the algorithm is to maintain a stack of bar indices. The stack helps in finding the next smaller bar (to the left and right) for each bar, which is essential for calculating the area of the rectangle with the current bar as the shortest bar. The extension of the heights array with a zero at the end ensures that all elements in the stack are processed.