O(m*n) time O(n) space C++ using Stack

  • 1
    int maximalRectangle(vector<vector<char>>& matrix) {
            if(!matrix.size()) return 0;
            vector<int> height(matrix[0].size()+1); // extra element because I am considering the area till previous element
            int ans=0;
            for(int i=0;i<matrix.size();i++) {
                // Construct height array
                for(int j=0;j<matrix[i].size();j++) {
                    if(matrix[i][j]=='1') height[j]=height[j]+1;
                    else height[j]=0;
                // Find the largest histogram at this row
                stack<int> index;
                for(int j=0;j<height.size();j++) {
                    while(index.size()>0 && height[index.top()]>=height[j]) {
                        int h = height[index.top()];
                        int left_boundary = index.size()>0?index.top():-1;
                        ans = max(ans, h*(j-left_boundary-1));
            return ans;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.