Largest Rectangle in Histogram

Largest Rectangle in Histogram

The Largest Rectangle in Histogram problem asks us to find the area of the largest rectangle that can be formed within the bounds of a given histogram. A histogram is represented by an array of integers, where each integer denotes the height of a bar. All bars have a width of 1.

The Brute Force Approach

A naive solution would involve checking every possible pair of bars and calculating the minimum height between them to find the area. This approach has a time complexity of O(N^2), which is inefficient for large histograms.

Optimized Approach: The Monotonic Stack

We can solve this problem in O(N) time using a Monotonic Increasing Stack. A monotonic increasing stack is a stack whose elements are always sorted in an increasing order from bottom to top.

The key observation is that the maximum area rectangle that includes a specific bar `i` will have a height equal to `histogram[i]`. Its width will extend to the left until it hits a bar shorter than `histogram[i]` and to the right until it hits another bar shorter than `histogram[i]`.

The stack helps us efficiently find the Next Smaller Element (NSE) and Previous Smaller Element (PSE) for every bar.

How it Works

1. Iterate through the histogram from left to right (index `0` to `n`).
2. 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, we push the current index onto the stack. We maintain an increasing order.
3. If the current bar is shorter than the bar at the top of the stack, it means the current bar is the Next Smaller Element (NSE)for the bar at the stack's top.
4. We start popping elementsfrom the stack. For every popped element (let's say its index is `poppedIndex`):
   • The height of the rectangle is histogram[poppedIndex].
   • The Next Smaller Element (NSE) is the current index we are at (let's call it `i`).
   • The Previous Smaller Element (PSE) is the new top of the stack after popping. If the stack becomes empty, it means there are no smaller elements to the left, so the left boundary is -1.
   • The width of the rectangle is calculated as: width = NSE - PSE - 1.
   • The area is height × width. We update our maximum area if this calculated area is larger.
5. We continue popping and calculating area as long as the stack is not empty and the current bar is shorter than the top of the stack. Then, we push the current index.
6. After iterating through all bars, we may still have elements in the stack. We pop them one by one, treating the right boundary as the end of the histogram (index `n`).

Complexity Analysis

• Time Complexity: O(N) - Every element is pushed and popped from the stack exactly once. Therefore, the operations are linear.
• Space Complexity: O(N) - The stack can hold up to `N` elements in the worst case (e.g., if the histogram is sorted in ascending order).