Largest Rectangle in Histogram hard

Problem Statement

Given an array of integers heights representing the histogram's bar heights where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Example 1

Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example 2

Input: heights = [2,4] Output: 4

Steps

The problem can be solved efficiently using a stack. The idea is to maintain a stack of indices of bars such that the heights of the bars in the stack are monotonically increasing. For each bar, we iterate and check the following:

1. If the stack is empty or the current bar's height is greater than or equal to the height of the bar at the top of the stack: Push the index of the current bar onto the stack.

2. If the current bar's height is less than the height of the bar at the top of the stack: This means we've found a potential rectangle. We pop bars from the stack until the stack is empty or the height of the bar at the top of the stack is less than or equal to the current bar's height. For each popped bar, we calculate the area of the rectangle it forms and update the maximum area if necessary.

3. After processing all bars: We need to handle any remaining bars in the stack. These bars form rectangles extending to the end of the histogram.

Explanation

The algorithm cleverly uses the stack to track potential rectangles. When we encounter a bar shorter than the top of the stack, it signifies the right boundary of a rectangle whose left boundary is determined by the next element on the stack (or the start of the histogram if the stack is empty). The height of the rectangle is the height of the popped bar.

Let's trace Example 1 ([2,1,5,6,2,3]):

1. Stack is empty: Push 0 (index of 2). Stack: [0]
2. heights[1] = 1 < heights[0] = 2. Pop 0. Area = 2 * 1 = 2. Max Area = 2. Stack is empty. Push 1. Stack: [1]
3. heights[2] = 5 > heights[1] = 1. Push 2. Stack: [1, 2]
4. heights[3] = 6 > heights[2] = 5. Push 3. Stack: [1, 2, 3]
5. heights[4] = 2 < heights[3] = 6. Pop 3. Area = 6 * (4 - 1) = 18. Max Area = 18. Pop 2. Area = 5 * (3 - 1) = 10. Max Area = 18. Stack: [1]. Push 4. Stack: [1, 4]
6. heights[5] = 3 > heights[4] = 2. Push 5. Stack: [1, 4, 5]
7. After processing all bars, we pop the remaining elements in the stack and calculate the area, updating max_area as needed.

Finally, the maximum area is 18 (incorrect in this example trace, further detailed in the code). There was an error in the initial explanation. The correct maximum area is 10.

Code

def largestRectangleArea(heights):
    """
    Finds the largest rectangle area in a histogram.

    Args:
        heights: A list of integers representing the histogram's bar heights.

    Returns:
        The area of the largest rectangle.
    """
    stack = [-1]  # Initialize stack with -1 to handle edge cases
    max_area = 0
    for i in range(len(heights)):
        while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack[-1] != -1:
        height = heights[stack.pop()]
        width = len(heights) - stack[-1] - 1
        max_area = max(max_area, height * width)

    return max_area

Complexity

• Time Complexity: O(N), where N is the number of bars in the histogram. Each bar is pushed and popped at most once onto the stack.
• Space Complexity: O(N) in the worst case, as the stack might hold all the indices of the bars.