85. Maximal Rectangle

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.

• Time : O(n^2 * m)
• Space : O(nm)

c++

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m,0));
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(matrix[i][j] != '1') continue;
                dp[i][j] = 1 + (j ? dp[i][j-1] : 0);
                res = max(dp[i][j], res);
                int mi = dp[i][j];
                for(int k = i - 1; k >= 0 and dp[k][j]; k--) {
                    mi = min(mi, dp[k][j]);
                    res = max(res, mi * (i - k + 1));
                }
            }
        }
        return res;
    }
};