Square of Zeroes

• Time : O(n n min(dp row, dp col))
• Space : O(n^2)

using namespace std;

bool squareOfZeroes(vector<vector<int>> matrix) {
    int n = matrix.size();
    vector<vector<int>> row(n, vector<int>(n, 0)), col(n, vector<int>(n, 0));

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(matrix[i][j]) continue;
            row[i][j] = (j ? row[i][j-1] : 0) + 1;
            col[i][j] = (i ? col[i-1][j] : 0) + 1;

            int mi = min(row[i][j], col[i][j]);

            for(int k = 1; k < mi; k++) {
                if(col[i][j-k] > k and row[i-k][j] > k)
                    return true;
            }
        }
    }

    return false;
}