C++ O(N) space solution


  • 0
    H

    dp[i][j] means the longest length of square which ends at matrix[i][j].
    We only need a one-row vector, and keep updating it.

    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int maxlen = 0;
            if(matrix.empty()) return maxlen;
            int m = matrix.size(), n = matrix[0].size(); 
            vector<int> dp(n+1, 0);
            for(int i = 0; i < m; i ++) {
                int pre = 0;
                for(int j = 1; j <= n; j ++) {
                    int tmp = dp[j];
                    if(matrix[i][j-1] == '1') {
                        dp[j] = min(pre, min(dp[j], dp[j-1])) + 1;
                        maxlen = max(maxlen, dp[j]);
                    }
                    else dp[j] = 0;
                    pre = tmp;
                }
            }
            return maxlen * maxlen;
        }
    };
    

Log in to reply
 

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