Largest Rectangle in Histogram

Problem Link: Leetcode

Problem Statement

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

Solution

Approach 1: Brute Force

The brute force approach is to consider every possible rectangle that can be formed from the given heights.

/*


*/
class Solution {
public:
    int largestRectangleAreaBruteForce(vector<int>& heights) {
        int maxArea = 0;
        int n = heights.size();
        for (int i = 0; i < n; i++) {
            int area = heights[i];
            int minHeight = heights[i];
            for (int j = i; j < n; j++) {
                minHeight = min(minHeight, heights[j]);
                area = (j - i + 1) * minHeight;
                maxArea = max(maxArea, area);
                if ((n - i) * minHeight < maxArea) {
                    break;
                }
            }
        }
        return maxArea;
    }

    int largestRectangleArea(vector<int>& heights) {
        return largestRectangleAreaBruteForce(heights);
    }
};

Approach 2: Using Two Monotonous Stacks

class Solution {
public:
    vector<int> nextSmallerElement(vector<int>& h) {
        int n = h.size();
        vector<int> smallerElementPos(n, n);

        stack<int> s;
        for (int i = n-1; i >= 0; i--) {
            // not interested in bigger numbers
            while (s.size() && h[s.top()] >= h[i]) {
                s.pop();
            }
            if (s.size()) {
                smallerElementPos[i] = s.top();
            }
            s.push(i);
        }

        return smallerElementPos;
    }

    vector<int> previousSmallerElement(vector<int>& h) {
        int n = h.size();
        vector<int> smallerElementPos(n, -1);

        stack<int> s;
        for (int i = 0; i < n; i++) {
            while (s.size() && h[s.top()] >= h[i]) {
                s.pop();
            }
            if (s.size()) {
                smallerElementPos[i] = s.top();
            }
            s.push(i);
        }
        return smallerElementPos;
    }

    int largestRectangleArea(vector<int>& heights) {
        return largestRectangleAreaUsingTwoStacks(heights);
    }

    int largestRectangleAreaUsingTwoStacks(vector<int>& heights) {
        
        auto pre = previousSmallerElement(heights);
        auto post = nextSmallerElement(heights);
        int n = heights.size();

        int result = 0;

        for (int i = 0; i < n; i++) {
            int start = pre[i];
            int end = post[i];
            int width = end - 1 - start;
            int area = width * heights[i];
            result = max(result, area);
        }
        return result;

    }
};