12. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example 1:

Input: [2,1,5,6,2,3]
Output: 10

Example 2:

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

Solution I: (Brute Force)

Algorithm:

Find the max area for a bar

Finding the leftmost valid limit Finding the rightmost valid limit Finding the area

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

        for (int i = 0; i < heights.size(); i++)
        {

            //Finding left most limit
            int j, k;
            for (j = i; j >= 0; j--)
            {
                if (heights[j] < heights[i])
                {
                    break;
                }
            }

            j++;

            //Finding right most limit

            for (k = i; k < heights.size(); k++)
            {
                if (heights[k] < heights[i])
                {
                    break;
                }
            }

            k--;

            int area = (k - j + 1) * heights[i];
            if (area > maxArea)
            {
                maxArea = area;
            }
        }

        return maxArea;
    }
};

Time Complexity: O(n^2)

Solution II: (Using Stack)

class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {

        stack<int> s;
        stack<int> r;

        int n = heights.size();
        vector<int> li(n);
        vector<int> ri(n);

        int maxArea = INT_MIN;

        //Left Starting point
        for (int i = 0; i < heights.size(); i++)
        {
            if (s.empty())
            {
                li[i] = 0;
                s.push(i);
            }
            else
            {
                if (heights[s.top()] < heights[i])
                {
                    li[i] = s.top() + 1;
                    s.push(i);
                }
                else
                {
                    while (!s.empty() && heights[s.top()] >= heights[i])
                    {
                        s.pop();
                    }
                    if (s.empty())
                    {
                        li[i] = 0;
                    }
                    else
                    {
                        li[i] = s.top() + 1;
                    }
                    s.push(i);
                }
            }
        }

        //right starting point
        for (int i = heights.size() - 1; i >= 0; i--)
        {
            if (r.empty())
            {
                ri[i] = n - 1;
                r.push(i);
            }
            else
            {
                if (heights[r.top()] < heights[i])
                {
                    ri[i] = r.top() - 1;
                    r.push(i);
                }
                else
                {
                    while (!r.empty() && heights[r.top()] >= heights[i])
                    {
                        r.pop();
                    }
                    if (r.empty())
                    {
                        ri[i] = n - 1;
                    }
                    else
                    {
                        ri[i] = r.top() - 1;
                    }
                    r.push(i);
                }
            }
        }

        for (int i = 0; i < ri.size(); i++)
        {

            int area = (ri[i] - li[i] + 1) * heights[i];
            if (area > maxArea)
            {
                maxArea = area;
            }
        }

        return maxArea;
    }
};

Time Complexity: O(n)