Description
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
Constraints:
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1
Solutions
Solution 1: Dynamic Programming
We define f[i][j] as the side length of the square submatrix with (i,j) as the bottom-right corner. Initially f[i][j] = 0, and the answer is ∑_{i,j} f[i][j].
Consider how to perform state transition for f[i][j].
- When matrix[i][j] = 0, we have f[i][j] = 0.
- When matrix[i][j] = 1, the value of state f[i][j] depends on the values of the three positions above, left, and top-left:
- If i = 0 or j = 0, then f[i][j] = 1.
- Otherwise f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1.
The answer is ∑_{i,j} f[i][j].
Time complexity O(m × n), space complexity O(m × n). Where m and n are the number of rows and columns of the matrix respectively.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
f = [[0] * n for _ in range(m)]
ans = 0
for i, row in enumerate(matrix):
for j, v in enumerate(row):
if v == 0:
continue
if i == 0 or j == 0:
f[i][j] = 1
else:
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
ans += f[i][j]
return ans(code-box)
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] f = new int[m][n];
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
continue;
}
if (i == 0 || j == 0) {
f[i][j] = 1;
} else {
f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
return ans;
}
}(code-box)
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int ans = 0;
vector<vector<int>> f(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
continue;
}
if (i == 0 || j == 0) {
f[i][j] = 1;
} else {
f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
return ans;
}
};(code-box)
func countSquares(matrix [][]int) int {
m, n, ans := len(matrix), len(matrix[0]), 0
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
for i, row := range matrix {
for j, v := range row {
if v == 0 {
continue
}
if i == 0 || j == 0 {
f[i][j] = 1
} else {
f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1
}
ans += f[i][j]
}
}
return ans
}(code-box)
function countSquares(matrix: number[][]): number {
const m = matrix.length;
const n = matrix[0].length;
const f: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
continue;
}
if (i === 0 || j === 0) {
f[i][j] = 1;
} else {
f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
return ans;
}(code-box)
impl Solution {
pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {
let m = matrix.len();
let n = matrix[0].len();
let mut f = vec![vec![0; n]; m];
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if matrix[i][j] == 0 {
continue;
}
if i == 0 || j == 0 {
f[i][j] = 1;
} else {
f[i][j] = std::cmp::min(f[i - 1][j - 1], std::cmp::min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
ans
}
}(code-box)
/**
* @param {number[][]} matrix
* @return {number}
*/
var countSquares = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
const f = Array.from({ length: m }, () => Array(n).fill(0));
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
continue;
}
if (i === 0 || j === 0) {
f[i][j] = 1;
} else {
f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i - 1][j], f[i][j - 1])) + 1;
}
ans += f[i][j];
}
}
return ans;
};(code-box)
public class Solution {
public int CountSquares(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
int[,] f = new int[m, n];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
continue;
}
if (i == 0 || j == 0) {
f[i, j] = 1;
} else {
f[i, j] = Math.Min(f[i - 1, j - 1], Math.Min(f[i - 1, j], f[i, j - 1])) + 1;
}
ans += f[i, j];
}
}
return ans;
}
}(code-box)
