DSA

Largest Rectangle in a Histogram

Covers: Brute Force, Using Stack, Optimal. Optimal — Time O(n), Space O(n).

August 8, 2026

Practice Link

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.

Brute Force#

You’re treating each bar at index i as the shortest bar in a rectangle and:

Looking Left:
- Move left from i, and count how far you can extend the rectangle until a smaller bar breaks the streak.
Looking Right:
- Move right from i, and do the same.
Area:
- The width of the rectangle is (left + right + 1) (including the current bar).
- So, area = height[i] * (left + right + 1).

cpp

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0;

        for(int i=0;i<heights.size();i++)
        {
            int left=0;
            for(int j=i-1;j>=0;j--)
                if(heights[j]>= heights[i])
                    left++;
                else
                    break;

            int right=0;
            for(int j=i+1;j<heights.size();j++)
                if(heights[j]>= heights[i])
                    right++;
                else
                    break;

            int area = heights[i] * (left+right+1);
            maxArea = max(area, maxArea);

        }
        return maxArea;
    }
};

Time Complexity: O(n^2)

Space Complexity: O(1)

Using Stack#

Pre-compute two arrays: leftSmall[i] (the leftmost index where the bar is as tall as heights[i]) and rightSmall[i] (the rightmost such index). A monotonic stack finds both boundaries in a single left-to-right and right-to-left pass respectively — when a smaller bar is encountered, all bars taller than it can never extend further, so they're popped. With both boundaries known, the area for each bar as the limiting height is heights[i] * (rightSmall[i] - leftSmall[i] + 1). This is O(n) overall but uses two separate stack passes and two auxiliary arrays of size n.

cpp

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0;
        int n = heights.size();

        stack<int> stk;
        vector<int> leftSmall(n), rightSmall(n);

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

            if(stk.empty())
                leftSmall[i]=0;
            else
                leftSmall[i] = stk.top()+1;

            stk.push(i);
        }

        while(!stk.empty())
            stk.pop();

        for(int i=n-1;i>=0;i--)
        {
            while(!stk.empty() && heights[stk.top()] >= heights[i])
                stk.pop();

            if(stk.empty())
                rightSmall[i]=n-1;
            else
                rightSmall[i] = stk.top()-1;

            stk.push(i);
        }

        for(int i=0;i<n;i++)
        {
            int area = (rightSmall[i]-leftSmall[i]+1) * heights[i];
            maxArea = max(area, maxArea);
        }
        return maxArea;
    }
};

Time Complexity: O(n) - Needs alot of traversal For finding leftSmaller -> O(n) + O(n), rightSmaller -> O(n) + O(n), finding area -> O(n)

Space Complexity: O(n)

Optimal Approach#

Combines the two-pass stack approach into a single left-to-right scan by computing the rectangle area on-the-fly when a bar is popped. When a shorter bar (or the sentinel at i == n) causes a pop, the popped bar's height is the limiting height; its width is the distance from the current index back to the new stack top. The key insight is that popping happens exactly when the maximum extent of a bar's rectangle is determined, eliminating the need for separate leftSmall/rightSmall arrays and reducing auxiliary space while keeping O(n) time.

cpp

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int maxArea = INT_MIN;

        stack<int> stk;

        for(int i = 0; i <= n; i++){

            while(!stk.empty() && (i == n || heights[stk.top()] >= heights[i])){
                int height = heights[stk.top()];
                stk.pop();

                int width = 0;

                if(stk.empty())
                    width = i;
                else
                    width = i - 1 - stk.top(); // from stk.top() + 1 to i - 1

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

Time Complexity: O(n)

Space Complexity: O(n)

DSAImplement Queue using StacksStacks & Queues. Space O(n).DSANext Greater Element IISolution - Monotonic Stack approach. Optimal — Time O(2n), Space O(n).DSADaily TemperatureCovers: Stack, Deque. Optimal — Time O(n), Space O(n).

Brute Force#

Using Stack#

Optimal Approach#

Related articles