One C++ Solution (O(m*n), O(1) Space)


  • 0
    5

    Since just using the space of matrix, tt is not really O(1) space.

    int maximalSquare(vector<vector<char>>& matrix) {
    	if (matrix.size() == 0) {
    		return 0;
    	}
    	int maxSquare = 0, rowLen = matrix.size(), colLen = matrix[0].size();
    	char *mat = &(matrix[0][0]), *pre = mat;
    	for (int col = 0; col < colLen; ++col) {
    	    mat[col] -= '0';
    	    maxSquare = !maxSquare && mat[col] ? mat[col] : maxSquare;
    	}
    	for (int row = 1; row < rowLen; ++row) {
    		mat = &(matrix[row][0]);
    		mat[0] -= '0';
    		maxSquare = !maxSquare && mat[0] ? mat[0] : maxSquare;
    		for (int col = 1; col < colLen; ++col) {
    		    mat[col] -= '0';
    			if (mat[col]) {
    				mat[col] = min(min(pre[col - 1], pre[col]), mat[col - 1]) + 1;
    				maxSquare = mat[col] > maxSquare ? mat[col] : maxSquare;
    			}
    		}
    		pre = mat;
    	}
    	return maxSquare*maxSquare;
    }

Log in to reply
 

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