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.

Examples

Example 1:

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

Explanation: The largest rectangle is highlighted, which has an area of 5*2 = 10 units.

Example 2:

Input: heights = [3, 5, 1, 7, 5, 9]
Output: 15

Explanation: The largest rectangle has an area of 5*3 = 15 units

Different Approaches

1️⃣ Brute Force Approach

Intuition:

One way to get the maximum rectangle area possible is by considering all the rectangles and then finding the maximum area out of those. To find the area of a rectangle, its height and width must be known. Already given the heights in the question, the only task remaining is to find the width of the rectangle.

The width of a rectangle of current height will depend on the number of rectangles on the left and right having a height greater than or equal to current height.

Understanding:

Consider the following example:

Hence, the width of the rectangle can be found using the concept of Previous/Next Smaller Elements. The formula for the same is:
      width = pse[ind] - nse[ind] - 1
where, pse[ind] and nse[ind] represent the indices of previous and next smaller element for current index.

Thus the indices of previous and next smaller elements can be precomputed. This will help in finding the area of individual rectangles possible, out of which the maximum can be returned as the answer.

Approach:

1. Find the indices of Next smaller elements and Previous smaller elements using Monotonic stack. For elements having no previous smaller element, use -1 as index. While for elements having no next smaller elements, use the size of array as index.
2. Use the precomputed NSE and PSE arrays to determine the width of the rectangle that each bar can form.
3. For each bar, calculate the area using its height and the distance between the NSE and PSE indices.
4. Keep track of the maximum area encountered during this process.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to find the indices of 
    next smaller elements */
    vector<int> findNSE(vector<int> &arr) {
        
        // Size of array
        int n = arr.size();
        
        // To store the answer
        vector<int> ans(n);
        
        // Stack 
        stack<int> st;
        
        // Start traversing from the back
        for(int i = n - 1; i >= 0; i--) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            element is not the smaller element */
            while(!st.empty() && arr[st.top()] >= arr[i]){
                st.pop();
            }
            
            // Update the answer
            ans[i] = !st.empty() ? st.top() : n;
            
            /* Push the index of current 
            element in the stack */
            st.push(i);
        }
        
        // Return the answer
        return ans;
    }
    
    /* Function to find the indices of 
    previous smaller elements */
    vector<int> findPSE(vector<int> &arr) {
        
        // Size of array
        int n = arr.size();
        
        // To store the answer
        vector<int> ans(n);
        
        // Stack 
        stack<int> st;
        
        // Traverse on the array
        for(int i=0; i < n; i++) {
            
            // Get the current element
            int currEle = arr[i];
            
            /* Pop the elements in the stack until 
            the stack is not empty and the top 
            elements is not the smaller element */
            while(!st.empty() && arr[st.top()] >= arr[i]){
                st.pop();
            }
            
            // Update the answer
            ans[i] = !st.empty() ? st.top() : -1;
            
            /* Push the index of current 
            element in the stack */
            st.push(i);
        }
        
        // Return the answer
        return ans;
    }
    
public:
    
    // Function to find the largest rectangle area
    int largestRectangleArea(vector<int> &heights) {
        
        /* Determine the next and 
        previous smaller elements */
        vector<int> nse = findNSE(heights);
        vector<int> pse = findPSE(heights);
        
        // To store largest area
        int largestArea = 0;
        
        // To store current area
        int area;
        
        // Traverse on the array
        for(int i=0; i < heights.size(); i++) {
            
            // Calculate current area
            area = heights[i] * (nse[i] - pse[i] - 1);
            
            // Update largest area
            largestArea = max(largestArea, area);
        }
        
        // Return largest area found
        return largestArea;
    }
};

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    // Function call to find the largest rectangle area
    int ans = sol.largestRectangleArea(heights);
    
    cout << "The largest rectangle area is: " << ans;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) (where N is the size of the given array)
  • Precomputing PSE and NSE arrays take O(2N) time each.
  • Traversing on the given histogram once to find the maximum area takes O(N) time.
• Space Complexity:O(N)
  • Finding the PSE and NSE arrays uses stack that takes O(N) space each.
  • Storing the PSE and NSE arrays take O(N) space each.

2️⃣ Optimal Approach

Intuition:

In the earlier solution, precomputing the PSE and NSE arrays was contributing to multiple traversals. This can be avoiding by finding the PSE on the go. But the question of finding the NSE still remains.

Understanding:

Consider the following dry run for finding the indices of previous smaller elements using Stack:

Hence, the index of NSE is known while popping the elements from the stack serving as a backward traversal. Hence, knowing the PSE and NSE, the width of the rectangle can be determined using the formula:
      width = pse[ind] - nse[ind] - 1
where, pse[ind] and nse[ind] represent the indices of previous and next smaller element for current index.

Handling remaining bars:

Since the areas of only those rectangles are considered which are popped from the stack, to ensure all the possible heights are considered for areas, all the elements must be popped from the stack even after the traversal of array is complete. For such elements (that remain in stack after traversal), the index of the next smaller element will be set to the size of array as there is no next smaller element.

Approach:

1. Initialize an empty stack to store indices of the histogram bars. For each height in the histogram, maintain a stack of indices where the heights are in increasing order.
2. If the current height is shorter than the height at the top of the stack, it means the rectangle with the height at the top of the stack ends at the current bar.
3. For each popped bar from the stack, calculate the width using the current index as the next smaller element (NSE) and the index of the new top of the stack as the previous smaller element (PSE).
4. Compute the area and update the maximum area found. After the traversal, the remaining bars in the stack have their NSE as the end of the array.
5. Calculate the area for these bars similarly and update the maximum area.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    // Function to find the largest rectangle area in a histogram
    int largestRectangleArea(vector<int> &heights) {

        int n = heights.size(); // Step 1: Get the number of bars in the histogram

        stack<int> st; // Step 2: Stack to store indices of histogram bars

        int largestArea = 0; // Step 3: To track the maximum area found so far
        int area; // Step 4: To store area for each candidate rectangle

        int nse, pse; // Step 5: NSE = Next Smaller Element index, PSE = Previous Smaller Element index

        // Step 6: Traverse each bar in the histogram
        for (int i = 0; i < n; i++) {

            // Step 7: While stack is not empty and current height is less than or equal to height at top index
            while (!st.empty() && heights[st.top()] >= heights[i]) {

                // Step 8: Pop the top index — this is the "height" of rectangle
                int ind = st.top(); 
                st.pop();

                // Step 9: Set PSE — if stack is empty, it's -1; else it's top of stack
                pse = st.empty() ? -1 : st.top();

                // Step 10: Set NSE — for the popped element, it's the current index
                nse = i;

                // Step 11: Calculate the area with height = heights[ind], width = nse - pse - 1
                area = heights[ind] * (nse - pse - 1);

                // Step 12: Update the max area
                largestArea = max(largestArea, area);
            }

            // Step 13: Push current index to the stack
            st.push(i);
        }

        // Step 14: Now process remaining bars in stack (they don’t have NSE during loop)
        while (!st.empty()) {

            // Step 15: NSE is beyond the end of the array
            nse = n;

            // Step 16: Get the top index from the stack
            int ind = st.top(); 
            st.pop();

            // Step 17: Set PSE again
            pse = st.empty() ? -1 : st.top();

            // Step 18: Calculate area for this bar
            area = heights[ind] * (nse - pse - 1);

            // Step 19: Update the max area
            largestArea = max(largestArea, area);
        }

        // Step 20: Return the final maximum area
        return largestArea;
    }
};

int main() {
    // Step 21: Sample histogram bars
    vector<int> heights = {2, 1, 5, 6, 2, 3};

    // Step 22: Create object of Solution class
    Solution sol;

    // Step 23: Call function to compute the largest rectangle area
    int ans = sol.largestRectangleArea(heights);

    // Step 24: Print the result
    cout << "The largest rectangle area is: " << ans;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) (where N is the size of the given array)
  • Traversing all the elements of array takes O(N) time.
  • All the elements are pushed in and popped out from stack once taking O(N) time.
• Space Complexity:O(N)
  • The stack space used to find the previous smaller element during traversal can go up to O(N).