Solution: Largest Rectangle in Histogram

Statement#

Given an array of integers, heights, that represents the heights of bars in a histogram, find the area of the largest rectangle in the histogram, where the rectangle has a constant width of $1$ unit for each bar.

Constraints

• $1 \leq$ heights.length $\leq 10^5$

• $0 \leq$ heights[i] $\leq 10^4$

Solution#

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

A naive approach is to consider every possible rectangle that can be formed in the histogram and compute the area of each rectangle. This involves iterating over all possible pairs of bars in the histogram and, for each pair, computing the height of the rectangle as the minimum height of the bar between them, and the width of the rectangle as the distance between them. The product of the height and width will give us the area of the rectangle for that pair. We return the rectangle with the maximum area.

This time complexity of this approach is $O(n^3)$, where $n$ is the number of bars in the histogram. This is because we use nested loops to iterate all the possible pairs of bars in the histogram, and for each pair, we iterate the bars between them to find the one with the minimum height.

The space complexity of this approach is $O(1)$ since a constant number of additional variables are used.

Optimized approach using stacks#

We can improve the naive approach by using stacks. The idea is that a rectangle's width can be maximized if it extends as far as possible to the left and right without encountering a bar shorter than the current rectangle's height. By iterating through the histogram bars, we maintain a stack of indices in increasing order of height. When encountering a bar shorter than the one at the top of the stack, we calculate the area of the rectangle formed by the popped height and the width between the current index and the index at the top of the stack. This process ensures that the algorithm explores potential rectangle formations at each bar's position while keeping track of the largest possible area seen so far. It capitalizes on the observation that a taller bar might provide opportunities for larger rectangles by extending to adjacent shorter bars.

Here's how the algorithm works:

• Create the following variables to assist the algorithm:

  • stack: This is the stack that will be used to store the indices of the bars. It is initialized to $-1$.

  • max_area: This will store the current maximum area of the rectangle as we traverse the heights array. It is initialized to $0$.

• Traverse the heights array from left to right:

  • If the current bar's height, height[i], is greater than that of the previous bar, height[i-1], the width of the rectangle of height, height[i-1], can be increased for a greater area. Therefore, we simply push the index of the current bar, i, to stack.

  • Otherwise, the current bar's height is less than that of the previous bar. This means that the maximum area of all the rectangles to the left of this bar can now be calculated. The following are the steps to calculate the area of each of these rectangles:

    • The top of stack, containing the index of the previous bar, will be popped.

    • The respective height at this index will become the current height of the rectangle.

    • The right boundary of this rectangle, i.e., the bar to its right is the current index i. It is stored in the right_boundary variable.

    • The left boundary of this rectangle, i.e., the bar to its left that will not be a part of this rectangle, is the index contained in the new top of stack. It is stored in the left_boundary variable.

    • The width of this rectangle is calculated using the formula: right_boundary - left_boundary - 1. $1$ is subtracted since neither of the bars at the boundary are included in the width.

    • The area of the rectangle is calculated by taking the product of the height and width.

    • Finally, we update max_area if the calculated area is greater than its existing value.

    • This process is repeated until the current bar's height is less than the top of the stack, after which it is pushed to the stack.

  • Repeat the process above until the array has been traversed completely.

• If stack contains elements other than -1, we have still not calculated the maximum area of the rectangle at all possible heights. Therefore, we calculate the area of the rectangle for all the heights of the remaining bars. The following are the steps to calculate these areas of each of these rectangles:

  • Pop from stack and calculate the maximum area of the rectangle of height corresponding to the index of the popped element.

  • The right boundary of this rectangle is the length of the heights array.

  • The left boundary of this rectangle is the index contained in the new top of stack. It is stored in the left_boundary variable

  • The width of this rectangle is calculated using the formula: len(heights) - left_boundary - 1.

  • The area of the rectangle is calculated by taking the product of the height and width.

  • Finally, we update max_area if the calculated area is greater than its existing value.

  • This process is repeated until the stack only contains -1, meaning that the maximum area of the rectangle at all possible heights has been calculated and evaluated.

• The max_area variable now stores the overall maximum area, so we return it.

The illustration below depicts how the algorithm runs:

Let’s look at the code for this solution below:

Solution summary#

The solution can be summarized in the following steps:

• Initialize a stack to $-1$ , and a variable to store the indices and to track the current maximum area, respectively.

• Loop through each bar's height in the histogram.

  • Push the current bar's index onto the stack if its height is greater than the one at the top of the stack.

  • Do the following until the stack is not empty and the current bar's height is less than the height at the top of the stack:

    • Pop bars from the stack and calculate the area of rectangles they form.

    • Update the maximum area if needed.

• After the loop, handle the remaining bars in the stack:

  • Calculate areas considering the rightmost boundaries.

  • Update the maximum area if needed.

• Return the maximum area calculated.

Time complexity#

The time complexity of this solution is $O(n)$, where $n$ is the number of bars in the histogram. This is because $n$ indices are pushed into and popped from the stack.

Space complexity#

The space complexity of this solution is $O(n)$, since a stack is used, where $n$ indices are pushed to it.