Largest Rectangle in Histogram hard

Problem Statement

Given an array of integers heights representing the histogram's bar height 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 largest rectangle is shown in the red area, and it has an area = 10 units.

Example 2

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

Steps

The key to solving this problem efficiently is using a stack to track potential rectangles. We iterate through the heights array. For each bar:

1. While the stack is not empty and the current bar's height is less than or equal to the height of the bar at the top of the stack: This means the current bar limits the height of the rectangle formed by the bars on the stack. We pop the bar from the stack and calculate the area of the rectangle it could form. The width of this rectangle is determined by the current index minus the index of the next bar on the stack (or 0 if the stack is now empty), and the height is the popped bar's height. We update the maximum area found so far.

2. Push the current bar's index onto the stack: This prepares for potential future rectangles.

3. After the loop: We need to handle any remaining bars on the stack. We repeat step 1, considering the right boundary as the end of the array.

Explanation

The algorithm uses a stack to efficiently track potential rectangles. By only considering bars that are shorter than previous ones, we avoid redundant calculations. The stack stores indices, not heights. This allows us to easily compute the width of a rectangle. The algorithm cleverly handles edge cases by iterating through the remaining stack elements after processing all bars. Each bar's potential contribution to the maximal area is examined only once.

Code

function largestRectangleArea(heights: number[]): number {
    const stack: number[] = [];
    let maxArea = 0;

    for (let i = 0; i <= heights.length; i++) {
        let height = (i === heights.length) ? 0 : heights[i]; // Handle the last bar

        while (stack.length > 0 && height < heights[stack[stack.length - 1]]) {
            let topIndex = stack.pop()!;
            let heightOfTop = heights[topIndex];
            let width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, heightOfTop * width);
        }
        stack.push(i);
    }

    return maxArea;
};

Complexity

• Time Complexity: O(n), where n is the number of bars in the histogram. Each bar is pushed and popped from the stack at most once.
• Space Complexity: O(n) in the worst case, as the stack could potentially store all the indices if the heights are monotonically increasing.