85. Maximal Rectangle

Problem Statement

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = [["0"]]
Output: 0

Example 3:

Input: matrix = [["1"]]
Output: 1

Constraints:

• rows == matrix.length

• cols == matrix[i].length

• 1 <= row, cols <= 200

• matrix[i][j] is '0' or '1'.

Intuition

Basically, Just make a count of buildings from 
that point

Converting the problem to Largest rectangle in Histogram

For eg->

For above figure the values would be
1 0 1 0 0
2 0 2 1 1 so on

Basically on those row arrays, we apply histogram logic

Links

https://leetcode.com/problems/maximal-rectangle/description/

Video Links

https://www.youtube.com/watch?v=tOylVCugy9k&ab_channel=takeUforward

Approach 1:

Monotonic Stack

C++

class Solution {
public:
    int rectangles_in_histogram(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;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> hist(m, vector<int>(n,0));

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

                for(int k=i; k>=0; k--){
                    if(matrix[k][j] == '1')
                        count++;

                    else 
                        break;
                }
                hist[i][j] = count;
            }
        }

        int maxi = 0;
        for(auto &it: hist){
            vector<int> temp(it);
            int ans = rectangles_in_histogram(it);

            maxi = max(maxi, ans);
        }
        
        return maxi;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems