Array
Dynamic Programming
Matrix
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 <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function countSquares ( matrix : number [][]) : number {
const [ m , n ] = [ matrix . length , matrix [ 0 ]. length ];
const f = Array . from ({ length : m }, () => Array ( n ));
const dfs = ( i : number , j : number ) : number => {
if ( i === m || j === n || ! matrix [ i ][ j ]) return 0 ;
f [ i ][ j ] ??= 1 + Math . min ( dfs ( i + 1 , j ), dfs ( i , j + 1 ), dfs ( i + 1 , j + 1 ));
return f [ i ][ j ];
};
let ans = 0 ;
for ( let i = 0 ; i < m ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
ans += dfs ( i , j );
}
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function countSquares ( matrix ) {
const [ m , n ] = [ matrix . length , matrix [ 0 ]. length ];
const f = Array . from ({ length : m }, () => Array ( n ));
const dfs = ( i , j ) => {
if ( i === m || j === n || ! matrix [ i ][ j ]) return 0 ;
f [ i ][ j ] ??= 1 + Math . min ( dfs ( i + 1 , j ), dfs ( i , j + 1 ), dfs ( i + 1 , j + 1 ));
return f [ i ][ j ];
};
let ans = 0 ;
for ( let i = 0 ; i < m ; i ++ ) {
for ( let j = 0 ; j < n ; j ++ ) {
ans += dfs ( i , j );
}
}
return ans ;
}
GitHub