Largest Rectangle in Histogram - Time Complexity: O(n), Language: C++

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 red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

Understanding the Problem

The core challenge of this problem is to find the largest rectangular area that can be formed within the histogram. This problem is significant in various fields such as computer graphics, data visualization, and computational geometry. A common pitfall is to attempt a brute-force solution, which would be inefficient for large inputs.

Approach

To solve this problem, we can use a stack-based approach which allows us to efficiently calculate the largest rectangle. The naive solution would involve checking all possible rectangles, which would be too slow for large arrays. Instead, we can use a stack to keep track of the indices of the histogram bars.

Naive Solution

The naive solution involves iterating over all pairs of bars and calculating the area for each possible rectangle. This approach has a time complexity of O(n^2) and is not feasible for large inputs.

Optimized Solution

The optimized solution uses a stack to keep track of the indices of the histogram bars. The idea is to maintain a stack of indices of the bars in increasing order of their heights. When we encounter a bar that is shorter than the bar at the top of the stack, we pop the stack and calculate the area of the rectangle formed with the popped bar as the smallest (or minimum height) bar. This ensures that we calculate the maximum area for each bar efficiently.

Algorithm

Here is a step-by-step breakdown of the stack-based algorithm:

Initialize an empty stack and a variable to store the maximum area.
Iterate through each bar in the histogram.
For each bar, if the stack is empty or the current bar is taller than the bar at the top of the stack, push its index onto the stack.
If the current bar is shorter, pop the stack and calculate the area of the rectangle with the popped bar as the smallest bar. Update the maximum area if necessary.
After processing all bars, pop the remaining bars in the stack and calculate the area for each.

Code Implementation

#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int largestRectangleArea(vector<int>& heights) {
    stack<int> s;
    int maxArea = 0;
    int n = heights.size();
    
    for (int i = 0; i <= n; ++i) {
        int h = (i == n ? 0 : heights[i]);
        while (!s.empty() && h < heights[s.top()]) {
            int height = heights[s.top()];
            s.pop();
            int width = s.empty() ? i : i - s.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        s.push(i);
    }
    
    return maxArea;
}

Complexity Analysis

The time complexity of the optimized solution is O(n) because each bar is pushed and popped from the stack at most once. The space complexity is O(n) due to the stack used to store the indices.

Edge Cases

Potential edge cases include:

All bars have the same height.
Bars are in increasing or decreasing order.
Single bar in the histogram.

Each of these cases is handled by the stack-based approach, ensuring the correct maximum area is calculated.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with a few bars.
Cases with all bars of the same height.
Cases with bars in increasing or decreasing order.
Large cases with up to 10^5 bars.

Using a testing framework like Google Test can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

Understand the problem constraints and requirements.
Consider both naive and optimized solutions.
Use data structures like stacks to manage and simplify the problem.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of finding the largest rectangle in a histogram. We explored a stack-based approach to solve the problem efficiently and provided a detailed explanation of the algorithm and its implementation in C++. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: