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, return 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 key idea to solve 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 is shorter than 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, calculate the area of the rectangle it forms, and update the maximum area if necessary. The width of this rectangle is the index difference between the current bar and the next bar on the stack (or the beginning of the array).

2. Push the current bar's index onto the stack: We push the index, not the height, because we need to know the position to calculate the width later.

3. After iterating through all bars: We need to handle any remaining bars on the stack. We repeat step 1, assuming a bar of height 0 at the end of the array.

Explanation

The algorithm cleverly uses a stack to keep track of potential rectangles. When we encounter a shorter bar, it means the height of the rectangle formed by the taller bars on the stack is limited. We pop those taller bars and calculate their areas, effectively finding the maximum area that can be formed using those bars. The process continues until the stack is empty or we find a bar that's taller than or equal to the current bar. Pushing the index onto the stack helps in calculating the width of the rectangles efficiently. The final iteration with an implicit height of 0 at the end handles any remaining bars on the stack.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int i = 0;

        while (i < heights.Length) {
            if (stack.Count == 0 || heights[stack.Peek()] <= heights[i]) {
                stack.Push(i++);
            } else {
                int top = stack.Pop();
                int area = heights[top] * (stack.Count == 0 ? i : i - stack.Peek() - 1);
                maxArea = Math.Max(maxArea, area);
            }
        }

        while (stack.Count > 0) {
            int top = stack.Pop();
            int area = heights[top] * (stack.Count == 0 ? i : i - stack.Peek() - 1);
            maxArea = Math.Max(maxArea, area);
        }

        return maxArea;
    }
}

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, the stack can hold all the indices of the bars.