Count Square Submatrices with All Ones
MediumArrayDynamic ProgrammingMatrix
Solution
export function countSquares(matrix: number[][]): number {
const [m, n] = [matrix.length, matrix[0].length];
let answer = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 1 && 0 < i && 0 < j) {
matrix[i][j] = Math.min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1]) + 1;
}
answer += matrix[i][j];
}
}
return answer;
}
Complexity
- Time:
O(NM)
- Space:
O(1)