Depth-First Search
Breadth-First Search
Union Find
Array
Matrix
Description
Given an m x n
2D binary grid grid
which represents a map of '1'
s (land) and '0'
s (water), return the number of islands .
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
is '0'
or '1'
.
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def numIslands ( self , grid : List [ List [ str ]]) -> int :
def dfs ( i , j ):
grid [ i ][ j ] = '0'
for a , b in pairwise ( dirs ):
x , y = i + a , j + b
if 0 <= x < m and 0 <= y < n and grid [ x ][ y ] == '1' :
dfs ( x , y )
ans = 0
dirs = ( - 1 , 0 , 1 , 0 , - 1 )
m , n = len ( grid ), len ( grid [ 0 ])
for i in range ( m ):
for j in range ( n ):
if grid [ i ][ j ] == '1' :
dfs ( i , j )
ans += 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class Solution {
private char [][] grid ;
private int m ;
private int n ;
public int numIslands ( char [][] grid ) {
m = grid . length ;
n = grid [ 0 ] . length ;
this . grid = grid ;
int ans = 0 ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' ) {
dfs ( i , j );
++ ans ;
}
}
}
return ans ;
}
private void dfs ( int i , int j ) {
grid [ i ][ j ] = '0' ;
int [] dirs = { - 1 , 0 , 1 , 0 , - 1 };
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ] ;
int y = j + dirs [ k + 1 ] ;
if ( x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == '1' ) {
dfs ( x , y );
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution {
public :
int numIslands ( vector < vector < char >>& grid ) {
int m = grid . size ();
int n = grid [ 0 ]. size ();
int ans = 0 ;
int dirs [ 5 ] = { -1 , 0 , 1 , 0 , -1 };
function < void ( int , int ) > dfs = [ & ]( int i , int j ) {
grid [ i ][ j ] = '0' ;
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ], y = j + dirs [ k + 1 ];
if ( x >= 0 && x < grid . size () && y >= 0 && y < grid [ 0 ]. size () && grid [ x ][ y ] == '1' ) {
dfs ( x , y );
}
}
};
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j =