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 = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' ) {
dfs ( i , j );
++ ans ;
}
}
}
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 func numIslands ( grid [][] byte ) int {
m , n := len ( grid ), len ( grid [ 0 ])
var dfs func ( i , j int )
dfs = func ( i , j int ) {
grid [ i ][ j ] = '0'
dirs := [] int { - 1 , 0 , 1 , 0 , - 1 }
for k := 0 ; k < 4 ; k ++ {
x , y := i + dirs [ k ], j + dirs [ k + 1 ]
if x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == '1' {
dfs ( x , y )
}
}
}
ans := 0
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if grid [ i ][ j ] == '1' {
dfs ( i , j )
ans ++
}
}
}
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 function numIslands ( grid : string [][]) : number {
const m = grid . length ;
const n = grid [ 0 ]. length ;
let ans = 0 ;
const dfs = ( i : number , j : number ) => {
if ( grid [ i ] ? .[ j ] !== '1' ) {
return ;
}
grid [ i ][ j ] = '0' ;
dfs ( i + 1 , j );
dfs ( i - 1 , j );
dfs ( i , j + 1 );
dfs ( i , j - 1 );
};
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] === '1' ) {
dfs ( i , j );
++ ans ;
}
}
}
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 const DIRS : [ i32 ; 5 ] = [ - 1 , 0 , 1 , 0 , - 1 ];
impl Solution {
pub fn num_islands ( grid : Vec < Vec < char >> ) -> i32 {
fn dfs ( grid : & mut Vec < Vec < char >> , i : usize , j : usize ) {
grid [ i ][ j ] = '0' ;
for k in 0 .. 4 {
let x = ( i as i32 ) + DIRS [ k ];
let y = ( j as i32 ) + DIRS [ k + 1 ];
if x >= 0
&& ( x as usize ) < grid . len ()
&& y >= 0
&& ( y as usize ) < grid [ 0 ]. len ()
&& grid [ x as usize ][ y as usize ] == '1'
{
dfs ( grid , x as usize , y as usize );
}
}
}
let mut grid = grid ;
let mut ans = 0 ;
for i in 0 .. grid . len () {
for j in 0 .. grid [ 0 ]. len () {
if grid [ i ][ j ] == '1' {
dfs ( & mut grid , i , j );
ans += 1 ;
}
}
}
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
34
35
36
37
38
39
40 using System ;
using System.Collections.Generic ;
using System.Linq ;
public class Solution {
public int NumIslands ( char [][] grid )
{
var queue = new Queue < Tuple < int , int >> ();
var lenI = grid . Length ;
var lenJ = lenI == 0 ? 0 : grid [ 0 ]. Length ;
var paths = new int [,] { { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, { - 1 , 0 } };
var result = 0 ;
for ( var i = 0 ; i < lenI ; ++ i )
{
for ( var j = 0 ; j < lenJ ; ++ j )
{
if ( grid [ i ][ j ] == '1' )
{
++ result ;
grid [ i ][ j ] = '0' ;
queue . Enqueue ( Tuple . Create ( i , j ));
while ( queue . Any ())
{
var position = queue . Dequeue ();
for ( var k = 0 ; k < 4 ; ++ k )
{
var next = Tuple . Create ( position . Item1 + paths [ k , 0 ], position . Item2 + paths [ k , 1 ]);
if ( next . Item1 >= 0 && next . Item1 < lenI && next . Item2 >= 0 && next . Item2 < lenJ && grid [ next . Item1 ][ next . Item2 ] == '1' )
{
grid [ next . Item1 ][ next . Item2 ] = '0' ;
queue . Enqueue ( next );
}
}
}
}
}
}
return result ;
}
}
Solution 2
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution :
def numIslands ( self , grid : List [ List [ str ]]) -> int :
def bfs ( i , j ):
grid [ i ][ j ] = '0'
q = deque ([( i , j )])
while q :
i , j = q . popleft ()
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' :
q . append (( x , y ))
grid [ x ][ y ] = 0
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' :
bfs ( 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
34
35
36
37
38
39 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' ) {
bfs ( i , j );
++ ans ;
}
}
}
return ans ;
}
private void bfs ( int i , int j ) {
grid [ i ][ j ] = '0' ;
Deque < int []> q = new ArrayDeque <> ();
q . offer ( new int [] { i , j });
int [] dirs = { - 1 , 0 , 1 , 0 , - 1 };
while ( ! q . isEmpty ()) {
int [] p = q . poll ();
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = p [ 0 ] + dirs [ k ] ;
int y = p [ 1 ] + dirs [ k + 1 ] ;
if ( x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == '1' ) {
q . offer ( new int [] { x , y });
grid [ x ][ y ] = '0' ;
}
}
}
}
}
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
34
35
36 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 ) > bfs = [ & ]( int i , int j ) {
grid [ i ][ j ] = '0' ;
queue < pair < int , int >> q ;
q . push ({ i , j });
vector < int > dirs = { -1 , 0 , 1 , 0 , -1 };
while ( ! q . empty ()) {
auto [ a , b ] = q . front ();
q . pop ();
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = a + dirs [ k ];
int y = b + dirs [ k + 1 ];
if ( x >= 0 && x < grid . size () && y >= 0 && y < grid [ 0 ]. size () && grid [ x ][ y ] == '1' ) {
q . push ({ x , y });
grid [ x ][ y ] = '0' ;
}
}
}
};
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' ) {
bfs ( i , j );
++ ans ;
}
}
}
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 func numIslands ( grid [][] byte ) int {
m , n := len ( grid ), len ( grid [ 0 ])
bfs := func ( i , j int ) {
grid [ i ][ j ] = '0'
q := [][] int {[] int { i , j }}
dirs := [] int { - 1 , 0 , 1 , 0 , - 1 }
for len ( q ) > 0 {
p := q [ 0 ]
q = q [ 1 :]
for k := 0 ; k < 4 ; k ++ {
x , y := p [ 0 ] + dirs [ k ], p [ 1 ] + dirs [ k + 1 ]
if x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == '1' {
q = append ( q , [] int { x , y })
grid [ x ][ y ] = '0'
}
}
}
}
ans := 0
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if grid [ i ][ j ] == '1' {
bfs ( i , j )
ans ++
}
}
}
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 function numIslands ( grid : string [][]) : number {
const m = grid . length ;
const n = grid [ 0 ]. length ;
let ans = 0 ;
function bfs ( i , j ) {
grid [ i ][ j ] = '0' ;
let q = [[ i , j ]];
const dirs = [ - 1 , 0 , 1 , 0 , - 1 ];
while ( q . length ) {
[ i , j ] = q . shift ();
for ( let k = 0 ; k < 4 ; ++ k ) {
const x = i + dirs [ k ];
const y = j + dirs [ k + 1 ];
if ( x >= 0 && x < m && y >= 0 && y < n && grid [ x ][ y ] == '1' ) {
q . push ([ x , y ]);
grid [ x ][ y ] = '0' ;
}
}
}
}
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' ) {
bfs ( i , j );
++ ans ;
}
}
}
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
34
35
36
37
38
39
40 use std :: collections :: VecDeque ;
const DIRS : [ i32 ; 5 ] = [ - 1 , 0 , 1 , 0 , - 1 ];
impl Solution {
pub fn num_islands ( grid : Vec < Vec < char >> ) -> i32 {
fn bfs ( grid : & mut Vec < Vec < char >> , i : usize , j : usize ) {
grid [ i ][ j ] = '0' ;
let mut queue = VecDeque :: from ([( i , j )]);
while ! queue . is_empty () {
let ( i , j ) = queue . pop_front (). unwrap ();
for k in 0 .. 4 {
let x = ( i as i32 ) + DIRS [ k ];
let y = ( j as i32 ) + DIRS [ k + 1 ];
if x >= 0
&& ( x as usize ) < grid . len ()
&& y >= 0
&& ( y as usize ) < grid [ 0 ]. len ()
&& grid [ x as usize ][ y as usize ] == '1'
{
grid [ x as usize ][ y as usize ] = '0' ;
queue . push_back (( x as usize , y as usize ));
}
}
}
}
let mut grid = grid ;
let mut ans = 0 ;
for i in 0 .. grid . len () {
for j in 0 .. grid [ 0 ]. len () {
if grid [ i ][ j ] == '1' {
bfs ( & mut grid , i , j );
ans += 1 ;
}
}
}
ans
}
}
Solution 3
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution :
def numIslands ( self , grid : List [ List [ str ]]) -> int :
def find ( x ):
if p [ x ] != x :
p [ x ] = find ( p [ x ])
return p [ x ]
dirs = ( 0 , 1 , 0 )
m , n = len ( grid ), len ( grid [ 0 ])
p = list ( range ( m * n ))
for i in range ( m ):
for j in range ( n ):
if grid [ i ][ j ] == '1' :
for a , b in pairwise ( dirs ):
x , y = i + a , j + b
if x < m and y < n and grid [ x ][ y ] == '1' :
p [ find ( i * n + j )] = find ( x * n + y )
return sum (
grid [ i ][ j ] == '1' and i * n + j == find ( i * n + j )
for i in range ( m )
for j in range ( n )
)
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
34
35
36
37
38
39
40
41
42 class Solution {
private int [] p ;
public int numIslands ( char [][] grid ) {
int m = grid . length ;
int n = grid [ 0 ] . length ;
p = new int [ m * n ] ;
for ( int i = 0 ; i < p . length ; ++ i ) {
p [ i ] = i ;
}
int [] dirs = { 1 , 0 , 1 };
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' ) {
for ( int k = 0 ; k < 2 ; ++ k ) {
int x = i + dirs [ k ] ;
int y = j + dirs [ k + 1 ] ;
if ( x < m && y < n && grid [ x ][ y ] == '1' ) {
p [ find ( x * n + y ) ] = find ( i * n + j );
}
}
}
}
}
int ans = 0 ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' && i * n + j == find ( i * n + j )) {
++ ans ;
}
}
}
return ans ;
}
private int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ] );
}
return p [ x ] ;
}
}
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
34
35
36 class Solution {
public :
int numIslands ( vector < vector < char >>& grid ) {
int m = grid . size ();
int n = grid [ 0 ]. size ();
vector < int > p ( m * n );
iota ( p . begin (), p . end (), 0 );
function < int ( int ) > find = [ & ]( int x ) -> int {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
};
int dirs [ 3 ] = { 1 , 0 , 1 };
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' ) {
for ( int k = 0 ; k < 2 ; ++ k ) {
int x = i + dirs [ k ];
int y = j + dirs [ k + 1 ];
if ( x < m && y < n && grid [ x ][ y ] == '1' ) {
p [ find ( x * n + y )] = find ( i * n + j );
}
}
}
}
}
int ans = 0 ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
ans += grid [ i ][ j ] == '1' && i * n + j == find ( i * n + 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36 func numIslands ( grid [][] byte ) int {
m , n := len ( grid ), len ( grid [ 0 ])
p := make ([] int , m * n )
for i := range p {
p [ i ] = i
}
var find func ( x int ) int
find = func ( x int ) int {
if p [ x ] != x {
p [ x ] = find ( p [ x ])
}
return p [ x ]
}
dirs := [] int { 1 , 0 , 1 }
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if grid [ i ][ j ] == '1' {
for k := 0 ; k < 2 ; k ++ {
x , y := i + dirs [ k ], j + dirs [ k + 1 ]
if x < m && y < n && grid [ x ][ y ] == '1' {
p [ find ( x * n + y )] = find ( i * n + j )
}
}
}
}
}
ans := 0
for i := 0 ; i < m ; i ++ {
for j := 0 ; j < n ; j ++ {
if grid [ i ][ j ] == '1' && i * n + j == find ( i * n + j ) {
ans ++
}
}
}
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
34
35
36
37 function numIslands ( grid : string [][]) : number {
const m = grid . length ;
const n = grid [ 0 ]. length ;
let p = [];
for ( let i = 0 ; i < m * n ; ++ i ) {
p . push ( i );
}
function find ( x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
}
const dirs = [ 1 , 0 , 1 ];
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' ) {
for ( let k = 0 ; k < 2 ; ++ k ) {
const x = i + dirs [ k ];
const y = j + dirs [ k + 1 ];
if ( x < m && y < n && grid [ x ][ y ] == '1' ) {
p [ find ( i * n + j )] = find ( x * n + y );
}
}
}
}
}
let ans = 0 ;
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
if ( grid [ i ][ j ] == '1' && i * n + j == find ( i * n + j )) {
++ ans ;
}
}
}
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
34
35
36
37
38
39
40
41
42 const DIRS : [ usize ; 3 ] = [ 1 , 0 , 1 ];
impl Solution {
pub fn num_islands ( grid : Vec < Vec < char >> ) -> i32 {
let m = grid . len ();
let n = grid [ 0 ]. len ();
let mut p : Vec < i32 > = ( 0 .. ( m * n ) as i32 ). collect ();
fn find ( p : & mut Vec < i32 > , x : usize ) -> i32 {
if p [ x ] != ( x as i32 ) {
p [ x ] = find ( p , p [ x ] as usize );
}
p [ x ]
}
for i in 0 .. m {
for j in 0 .. n {
if grid [ i ][ j ] == '1' {
for k in 0 .. 2 {
let x = i + DIRS [ k ];
let y = j + DIRS [ k + 1 ];
if x < m && y < n && grid [ x ][ y ] == '1' {
let f1 = find ( & mut p , x * n + y );
let f2 = find ( & mut p , i * n + j );
p [ f1 as usize ] = f2 ;
}
}
}
}
}
let mut ans = 0 ;
for i in 0 .. m {
for j in 0 .. n {
if grid [ i ][ j ] == '1' && p [ i * n + j ] == (( i * n + j ) as i32 ) {
ans += 1 ;
}
}
}
ans
}
}