Given an integer array heights, where heights[index] is the height of a histogram bar and every bar has width 1, find the largest area of a rectangle formed entirely from one or more consecutive bars.
Example 1
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: Bars with heights 5 and 6 support a rectangle of height 5 and width 2. The resulting area is 5 * 2 = 10.
Example 2
Input: heights = [0]
Output: 0
Explanation: A zero-height bar cannot support a rectangle with positive area.
Brute Force Approach
Every rectangle in a histogram is limited by its shortest bar. Therefore, each bar can be treated as the rectangle height, and the rectangle can expand left and right while the surrounding bars remain at least as tall.
This directly checks the widest rectangle supported by every bar. The method is easy to understand, but the same bars may be scanned repeatedly for different heights, making it slow for large histograms.
Algorithm
Initialize
maxArea = 0to store the largest rectangle area.Select every histogram bar as the limiting height of a possible rectangle.
Move
lefttoward the beginning while the previous bar is greater than or equal to the current height, because such bars can support the rectangle.Move
righttoward the end while the next bar is greater than or equal to the current height.Calculate the supported width as
right - left + 1, because this range contains all consecutive bars that support the current height.Calculate the area as
currentHeight × widthand updatemaxAreawhen a larger area is found.Return
maxAreaafter considering every bar as the limiting height.
Dry Run
Largest Rectangle Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the largest rectangle by boundary scans. long long largestRectangleArea(vector<int>& heights) { int n = heights.size(); long long maxArea = 0; // Treat every bar as the limiting height. for (int index = 0; index < n; index++) { int left = index; int right = index; // Extend across bars supporting the height. while (left > 0 && heights[left - 1] >= heights[index]) { left--; } // Extend across bars supporting the height. while (right + 1 < n && heights[right + 1] >= heights[index]) { right++; } long long width = right - left + 1; // The current bar limits the rectangle height. long long area = 1LL * heights[index] * width; // Preserve the best supported rectangle. maxArea = max(maxArea, area); } // Every limiting height has been checked. return maxArea; }};// Driver codeint main() { vector<int> heights = {2, 1, 5, 6, 2, 3}; Solution obj; cout << obj.largestRectangleArea(heights) << endl; return 0;}Note: Repeated boundary scans may fail for large input values. Quadratic work can cause an online judge to report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(N2), each of the n bars can trigger left and right scans across the complete histogram.
Space Complexity: O(1), only boundary indices and area values use auxiliary storage.
Optimal Approach
The repeated boundary searches can be removed by keeping unresolved bars in increasing height order. A shorter incoming bar closes every taller bar on the stack because the incoming index becomes the first smaller boundary on the right.
After a pop, the new stack top marks the first smaller boundary on the left. A final zero-height sentinel closes every remaining bar, allowing all areas to be calculated in one traversal.
Algorithm
Initialize an empty stack of indices and set
maxArea = 0to store the largest rectangle area found.Traverse indices from
0throughn, using height0at the extra sentinel index to force processing of all remaining bars.Pop stack indices while the corresponding heights are greater than or equal to the current height, because the current index becomes the first smaller boundary on the right.
Store the popped bar height and determine the left boundary from the new stack top.
Calculate width as
currentIndexwhen the stack becomes empty, or ascurrentIndex - stackTop - 1when a smaller bar remains on the left.Update
maxAreausingpoppedHeight × width, because the popped bar forms the limiting height across the calculated range.Push every real index after resolving taller or equal bars, then return
maxAreaafter the sentinel processes all remaining stack entries.
Dry Run
Largest Rectangle Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the largest rectangle with a stack. long long largestRectangleArea(vector<int>& heights) { int n = heights.size(); stack<int> indices; long long maxArea = 0; // Add a zero sentinel to close remaining bars. for (int index = 0; index <= n; index++) { int currentHeight = index == n ? 0 : heights[index]; // A shorter bar closes taller rectangles. while (!indices.empty() && heights[indices.top()] >= currentHeight) { int height = heights[indices.top()]; indices.pop(); // The new top is the smaller left boundary. int width = indices.empty() ? index : index - indices.top() - 1; // The popped bar limits the closed rectangle. long long area = 1LL * height * width; // Preserve the largest closed rectangle. maxArea = max(maxArea, area); } // Only real bar indices belong in the stack. if (index < n) { indices.push(index); } } // The sentinel has resolved every bar. return maxArea; }};// Driver codeint main() { vector<int> heights = {2, 1, 5, 6, 2, 3}; Solution obj; cout << obj.largestRectangleArea(heights) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), every bar index is pushed once and popped at most once.
Space Complexity: O(N), the monotonic stack can store all bar indices for nondecreasing heights.
Interview follow-up Questions
A histogram rectangle covers one continuous horizontal range. Skipping a bar would create a gap, so every bar between the left and right boundaries must have a height at least equal to the rectangle’s height.
Be the first to add a comment.