84. Largest Rectangle in Histogram

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

Constraints:

• 1 <= heights.length <= 105

• 0 <= heights[i] <= 104

Intuition

Approach 1: Brute Force
    
    Basically, You go to a elements left and right
    To find that elements range over the array
    
    Do this for each element and find maximum
    
    eg-> 2 1 9 6 7 3
    For 6 -> go left till you find lower element than that
    that is 1 here , in right 3 
    So take that width and multiply that value


Approach 2: Better (Monotonic stack)

    Maintain stack in increasing order, 
    Take same example,
    
    Find left smaller and right smaller using Stack
    Apply right - left * arr[i]
    
    For this 
    You pop, if the current element is smaller than stack top
    This means, let say 6 7 9 Then comes current as 1 , 
    We pop all beacuse
    
    max height now can only be 1

Approach 3: Optimal
    
    Rather than using two iterations to compute the 
    Leftsmall and rightsmall
    
    We As soon as we encounter smaller stack top than current 
    We know that element is  our right element for that stack top
    
    and for left element we look at the just below the stack top
    
    And story remains same

Links

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

Video Links

https://www.youtube.com/watch?v=X0X6G-eWgQ8&ab_channel=takeUforward https://www.youtube.com/watch?v=jC_cWLy7jSI&ab_channel=takeUforward

Approach 1:

Better

C++

class Solution {
public:
    int largestRectangleArea(vector<int>& arr) {
        int n = arr.size();
        vector<int> left(n), right(n);
        vector<int> ans(n);
        int maxi = 0;

        stack<int> st;

        for(int i=0; i<n; i++){
            while (!st.empty() and arr[st.top()] >= arr[i]) {
                st.pop();
            }

            if(st.empty())
                left[i] = 0;

            else
                left[i] = st.top() + 1;

            st.push(i);
        }

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

        for(int i=n-1; i>=0; i--){
            while (!st.empty() and arr[st.top()] >= arr[i]) {
                st.pop();
            }

            if(st.empty())
                right[i] = n-1;

            else
                right[i] = st.top() - 1;

            ans[i] = (right[i] - left[i] + 1) * arr[i];
            maxi = max(maxi, ans[i]);

            st.push(i);
        }

        return maxi;
    }
};

Approach 2:

Optimal

C++

class Solution {
  public:
    int largestRectangleArea(vector < int > & histo) {
      stack < int > st;
      int maxA = 0;
      int n = histo.size();
      for (int i = 0; i <= n; i++) {
        while (!st.empty() && (i == n || histo[st.top()] >= histo[i])) {
          int height = histo[st.top()];
          st.pop();
          int width;
          if (st.empty())
            width = i;
          else
            width = i - st.top() - 1;
          maxA = max(maxA, width * height);
        }
        st.push(i);
      }
      return maxA;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems