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 <= 1050 <= heights[i] <= 104The key challenge in Largest Rectangle in Histogram is efficiently determining the maximum rectangular area that can be formed using the histogram bars. A brute-force method checks every possible pair of boundaries and calculates the minimum height between them, but this leads to O(n^2) time complexity.
The optimal solution uses a monotonic increasing stack. The stack stores indices of histogram bars while maintaining increasing heights. When a new bar is shorter than the top of the stack, it means the rectangle using the taller bar as the limiting height must end there. By popping from the stack, we compute the rectangle width using the current index and the new top of the stack as boundaries.
This approach ensures each bar is pushed and popped at most once, giving an efficient O(n) time complexity. A small trick often used is adding a sentinel bar (height 0) at the end to flush remaining stack elements. The algorithm uses O(n) additional space for the stack.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (check all ranges) | O(n^2) | O(1) |
| Monotonic Stack | O(n) | O(n) |
Jackson Gabbard
This approach utilizes a monotonic stack to efficiently track the heights of the histogram bars. By iterating through the array and maintaining a stack of indices, we can pop the stack whenever we find a shorter bar, calculate the area of the rectangle formed with the popped bar as the shortest.bar and update the maximum area if necessary. The stack helps to find the left and right boundaries for each bar to compute the area.
Time Complexity: O(n), where n is the number of bars (height array length), since each bar is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack.
1#include <vector>
2#include <stack>
3#include <algorithm>
4#include <iostream>
5
6int largestRectangleArea(std::vector<int>& heights) {
7 std::stack<int> stk;
8 int max_area = 0;
9 int i = 0;
10
11 while (i < heights.size() || !stk.empty()) {
12 if (stk.empty() || (i < heights.size() && heights[i] >= heights[stk.top()])) {
13 stk.push(i++);
14 } else {
int h = heights[stk.top()];
stk.pop();
int width = stk.empty() ? i : i - stk.top() - 1;
max_area = std::max(max_area, h * width);
}
}
return max_area;
}
int main() {
std::vector<int> heights = {2,1,5,6,2,3};
std::cout << largestRectangleArea(heights) << std::endl;
return 0;
}The C++ solution operates similarly to the C solution, but leverages a stack from the STL to manage the bar indices. As we traverse the height array, when we encounter a bar shorter than the one indexed at the current top of the stack, we compute potential max areas, updating as necessary. Like the C approach, the max area is updated after assessing each possible rectangle and utilizes the breadth determined by the stack's index order.
This approach is inspired by the algorithm for finding the maximum subarray sum, with the core idea to exploit the properties of minimal elements acting as the constraints. Here, smaller segments of the array are divided to compute maximum rectangular areas separately and then to combine comprehensive results. It works optimally when the heights array is transformed to assist binary division, allowing recursive calls to determine the peak areas between and within divisions.
Time Complexity: O(n^2), with potential for worse case involving complete traversal checks.
Space Complexity: O(n) for recursive calls.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A monotonic stack maintains elements in sorted order, making it easier to detect when the order breaks. In histogram problems, it helps quickly find the previous and next smaller elements, which are essential for computing maximum rectangle widths.
Yes, this problem is commonly asked in FAANG and other top tech company interviews. It tests understanding of stacks, boundary calculations, and optimization from brute force to linear-time solutions.
A stack is the most suitable data structure, specifically a monotonic increasing stack. It helps efficiently track previous smaller bars and determine the maximum width for each height when a boundary is found.
The optimal approach uses a monotonic increasing stack to track bar indices. When a smaller bar appears, taller bars are popped and their rectangle areas are computed using the current index as the right boundary. This ensures each bar is processed once, achieving O(n) time complexity.
The Python function follows the divide and conquer rules established, determining minimum height within selected segments and solving for maximum rectangles via recursive advances into left and right segments. Using Python's max function ensures uniform maximum selection post evaluation.