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 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 problem can be solved efficiently using a stack. The key idea is to maintain a stack of indices of bars that are monotonically increasing in height. When we encounter a bar that is shorter than the bar at the top of the stack, it means we've found a potential rectangle. We pop bars from the stack until we find a bar that is shorter or the stack is empty. For each popped bar, we calculate the area of the rectangle it forms and update the maximum area.

Here's a breakdown of the steps:

1. Initialize a stack: Use an empty stack to store indices of bars.
2. Iterate through the heights array: For each bar heights[i]:
   • While the stack is not empty and the current bar is shorter than the bar at the top of the stack:
     • Pop the index j from the stack.
     • Calculate the width of the rectangle formed by the bar at index j: The width is i - stack.peek() - 1 if the stack is not empty, otherwise it's i.
     • Calculate the area: heights[j] * width.
     • Update the maximum area if necessary.
   • Push the current bar's index i onto the stack.
3. After iterating through all bars: Process any remaining bars in the stack (similar to step 2).
4. Return the maximum area.

Explanation

The stack maintains a sequence of indices representing increasing heights. When a shorter bar is encountered, it limits the height of rectangles formed by the taller bars preceding it. By popping these taller bars and calculating their areas, we effectively find all possible rectangles that can be formed with those bars as their height.

Code

import java.util.Stack;

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

        while (i < heights.length) {
            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, area);
            }
        }

        while (!stack.isEmpty()) {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);
        }

        return maxArea;
    }
}

Complexity

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