DSA

Maximum Rectangle in Histogram

Better approach. Optimal — Time O(n), Space O(1).

August 8, 2026
DSAStackQueueLeetCodePractice

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.

Initiution#

  • We check for every bar height, what will be the width.
  • To check the width, we are interested in the previous smaller height(element) and next smaller height(element) -> limits.
  • Find PSE and NSE and width = nse-pse-1 -> requires precomputation

Solution#

cpp
class Solution {
public:
    void findNSE(vector<int>& nse, vector<int>& heights){
        int n = heights.size();
        stack<int> st;
        for(int i = n-1; i >= 0; i--){
            while(!st.empty() && heights[st.top()] >= heights[i]){
                st.pop();
            }
            if(!st.empty()){
                nse[i] = st.top();
            }
            else{
                nse[i] = n;
            }
            st.push(i);
        }
    }
    void findPSE(vector<int>& pse, vector<int>& heights){
        int n = heights.size();
        stack<int> st;
        for(int i = 0; i < n; i++){
            while(!st.empty() && heights[st.top()] >= heights[i]){
                st.pop();
            }
            if(!st.empty()){
                pse[i] = st.top();
            }
            else{
                pse[i] = -1;
            }
            st.push(i);
        }
    }
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int>nse(n);
        vector<int>pse(n);
        findNSE(nse, heights);
        findPSE(pse, heights);
        
        int maxi = 0;
        for(int i = 0; i < n; i++){
            maxi = max(maxi, heights[i]*(nse[i] - pse[i] -1));
        }
        return maxi;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Better Solution#

Instead of two separate precomputation passes (PSE and NSE arrays), compute the rectangle area on the fly with a single monotonic stack traversal. The stack holds bar indices in increasing order of height. When a shorter bar is encountered (or when we reach the end of the array, treated as height 0), every bar on the stack that is taller than the current bar has found its Next Smaller Element. At that point its Previous Smaller Element is simply the new top of the stack after popping. Width is therefore i - stack.top() - 1 (or i if the stack is empty), and the rectangle area can be computed immediately. This eliminates the PSE/NSE arrays and reduces space from O(n) to O(n) stack only — with no extra arrays.

cpp
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0, area, height, width;
        stack<int> stk;

        for(int i=0;i<=heights.size();i++)
        {
            while(!stk.empty() && (i==heights.size() || heights[stk.top()] >= heights[i])){
                height = heights[stk.top()];
                stk.pop();

                if(stk.empty())
                    width = i;
                else
                    width = i - stk.top() -1;

                area = height * width;
                maxArea = max(area, maxArea);
            }
            stk.push(i);
        }
        return maxArea;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Related articles

DSAImplement Queue using StacksStacks & Queues. Space O(n).DSANext Greater Element IISolution - Monotonic Stack approach. Optimal — Time O(2n), Space O(n).DSALargest Rectangle in a HistogramCovers: Brute Force, Using Stack, Optimal. Optimal — Time O(n), Space O(n).