Largest Rectangle In Histogram Solution in Python

In the “Largest Rectangle in Histogram” problem, we are given an array of integers representing the heights of bars in a histogram.

Question: 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.

So, each bar has a width of 1 unit, and our goal is to find the largest rectangle that can be formed within the histogram and return its area.

For example, given the input array heights = [2,1,5,6,2,3], the largest rectangle that can be formed has an area of 10, as shown below:

    6
  +---+
  |   |   5
  |   | +---+
  |   | |   |
  |   | |   |
2 |   | |   |
+---+ | |   |
|   | | |   |
| 1 | | |   |
+---+ | |   |
|   | | |   |
|   | | |   |
|   | | |   |

Example:

Input:

heights = [2,1,5,6,2,3]

Output:

Constraints:

The length of the heights array is between 1 and 105.
The height of each bar is between 0 and 104.

Understanding the Constraints

Before we dive into the solution, let’s understand the constraints of this problem:

The number of elements in the heights array can be as large as 105, which means our solution should be efficient enough to handle a large input size without exceeding time limits.
The height of each bar can range from 0 to 104, so we need to consider various height scenarios when designing our algorithm.
Since we are dealing with a histogram, we can assume that the widths of the bars are always 1 unit.

Largest Rectangle In Histogram LeetCode Problem Solution

Now, let’s explore the efficient approach to solving the “Largest Rectangle in Histogram” problem.

We’ll use a stack-based algorithm to find the solution.

1. Bruteforce Approach

Before we dive into the efficient approach, let’s briefly discuss a brute-force approach to solving this problem.

The brute force approach would involve considering every possible pair of bars and calculating the area of the rectangle formed by those two bars.

We would repeat this process for all pairs of bars and keep track of the maximum area found.

However, this approach would have a time complexity of O(n^2), where n is the number of bars, making it highly inefficient for large inputs.

Therefore, we’ll focus on a more efficient approach.

2. Efficient Approach using a Stack

To find the largest rectangle efficiently, we’ll use a stack-based algorithm.

The idea is to maintain a stack of indices while iterating through the heights array.

We’ll keep track of the indices of the bars in increasing order of their heights.

Here’s a step-by-step breakdown of our efficient approach:

Initialize a stack to store pairs of indices and heights.

Initialize a variable max_area to keep track of the maximum area found, initially set to 0.

Iterate through the heights array from left to right:

For each bar at index i, compare its height with the height of the bar at the top of the stack (if the stack is not empty).
If the current bar’s height is greater than the height at the top of the stack, push the current bar’s index and height onto the stack.
If the current bar’s height is less than or equal to the height at the top of the stack, it indicates that we cannot extend the rectangle to the right anymore. In this case, pop elements from the stack and calculate the area of the rectangles that ended at those popped bars. Update max_area with the maximum area found during this process.

After processing all bars, there might still be some bars left in the stack.

These bars can be extended to the end of the histogram.

Pop each remaining bar from the stack, calculate its area, and update max_area if a larger area is found.

Return the value of max_area as the result.

Let’s implement this algorithm in Python:

View on GitHub ➹

def largestRectangleArea(self, heights: List[int]) -> int:
    max_area = 0
    stack = []  # stack to store pairs: (index, height)

    for i, height in enumerate(heights):
        start = i
        while stack and stack[-1][1] > height:
            index, h = stack.pop()
            max_area = max(max_area, h * (i - index))
            start = index
        stack.append((start, height))

    for index, height in stack:
        max_area = max(max_area, height * (len(heights) - index))
    
    return max_area

This efficient approach uses a stack to keep track of potential rectangles and achieves a time complexity of O(n), where n is the number of bars in the histogram.

Time and Space Complexity

The time complexity of our efficient solution is O(n) because we iterate through the heights array once, and each element is pushed onto the stack and popped from the stack at most once.

The space complexity is also O(n) because, in the worst case, all elements of the heights array could be pushed onto the stack.

Reasoning Behind Our Approach

The reasoning behind our approach lies in the observation that we can efficiently find the largest rectangle by maintaining a stack of indices and heights.

We use this stack to keep track of the bars that can potentially contribute to the largest rectangle.

When we encounter a bar with a smaller height, we can calculate the area of the rectangles that ended at the previous bars with greater heights, as these rectangles cannot be extended further to the right.

By doing this, we ensure that we consider all possible rectangles and find the largest one.

Conclusion

In this guide, we have explored the “Largest Rectangle in Histogram” problem and provided a step-by-step explanation of an efficient solution using a stack-based algorithm.

We discussed the constraints of the problem, the brute force approach, and the reasoning behind our efficient approach.

By using this approach, you can efficiently find the largest rectangle in a histogram, making it suitable for solving this problem with large input sizes.

You can now submit a Largest Rectangle In Histogram solution to LeetCode today.

If you have any questions, suggestions, or comments, please feel free to share them below.

Happy coding!