Depth-First Search
Breadth-First Search
Union Find
Array
Matrix
Description
You are given an m x n
binary matrix grid
. An island is a group of 1
's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1
in the island.
Return the maximum area of an island in grid
. If there is no island, return 0
.
Example 1:
Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j]
is either 0
or 1
.
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def maxAreaOfIsland ( self , grid : List [ List [ int ]]) -> int :
def dfs ( i : int , j : int ) -> int :
if grid [ i ][ j ] == 0 :
return 0
ans = 1
grid [ i ][ j ] = 0
dirs = ( - 1 , 0 , 1 , 0 , - 1 )
for a , b in pairwise ( dirs ):
x , y = i + a , j + b
if 0 <= x < m and 0 <= y < n :
ans += dfs ( x , y )
return ans
m , n = len ( grid ), len ( grid [ 0 ])
return max ( dfs ( i , 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 class Solution {
private int m ;
private int n ;
private int [][] grid ;
public int maxAreaOfIsland ( int [][] 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 ) {
ans = Math . max ( ans , dfs ( i , j ));
}
}
return ans ;
}
private int dfs ( int i , int j ) {
if ( grid [ i ][ j ] == 0 ) {
return 0 ;
}
int ans = 1 ;
grid [ i ][ j ] = 0 ;
int [] dirs = { - 1 , 0 , 1 , 0 , - 1 };
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ] , y = j + dirs [ k + 1 ] ;
if ( x >= 0 && x < m && y >= 0 && y < n ) {
ans += dfs ( x , y );
}
}
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 class Solution {
public :
int maxAreaOfIsland ( vector < vector < int >>& grid ) {
int m = grid . size (), n = grid [ 0 ]. size ();
int dirs [ 5 ] = { -1 , 0 , 1 , 0 , -1 };
int ans = 0 ;
function < int ( int , int ) > dfs = [ & ]( int i , int j ) {
if ( grid [ i ][ j ] == 0 ) {
return 0 ;
}
int ans = 1 ;
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 < m && y >= 0 && y < n ) {
ans += dfs ( x , y );
}
}
return ans ;
};
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
ans = max ( ans , dfs ( 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
23
24
25 func maxAreaOfIsland ( grid [][] int ) ( ans int ) {
m , n := len ( grid ), len ( grid [ 0 ])
dirs := [ 5 ] int { - 1 , 0 , 1 , 0 , - 1 }
var dfs func ( i , j int ) int
dfs = func ( i , j int ) int {
if grid [ i ][ j ] == 0 {
return 0
}
ans := 1
grid [ i ][ j ] = 0
for k := 0 ; k < 4 ; k ++ {
x , y := i + dirs [ k ], j + dirs [ k + 1 ]
if x >= 0 && x < m && y >= 0 && y < n {
ans += dfs ( x , y )
}
}
return ans
}
for i := range grid {
for j := range grid [ i ] {
ans = max ( ans , dfs ( i , j ))
}
}
return
}
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 function maxAreaOfIsland ( grid : number [][]) : number {
const m = grid . length ;
const n = grid [ 0 ]. length ;
const dirs = [ - 1 , 0 , 1 , 0 , - 1 ];
const dfs = ( i : number , j : number ) : number => {
if ( grid [ i ][ j ] === 0 ) {
return 0 ;
}
let ans = 1 ;
grid [ i ][ j ] = 0 ;
for ( let k = 0 ; k < 4 ; ++ k ) {
const [ x , y ] = [ i + dirs [ k ], j + dirs [ k + 1 ]];
if ( x >= 0 && x < m && y >= 0 && y < n ) {
ans += dfs ( x , y );
}
}
return ans ;
};
let ans = 0 ;
for ( let i = 0 ; i < m ; ++ i ) {
for ( let j = 0 ; j < n ; ++ j ) {
ans = Math . max ( ans , dfs ( 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
23
24
25
26
27
28 impl Solution {
fn dfs ( grid : & mut Vec < Vec < i32 >> , i : usize , j : usize ) -> i32 {
if i == grid . len () || j == grid [ 0 ]. len () || grid [ i ][ j ] == 0 {
return 0 ;
}
grid [ i ][ j ] = 0 ;
let mut res = 1 + Self :: dfs ( grid , i + 1 , j ) + Self :: dfs ( grid , i , j + 1 );
if i != 0 {
res += Self :: dfs ( grid , i - 1 , j );
}
if j != 0 {
res += Self :: dfs ( grid , i , j - 1 );
}
res
}
pub fn max_area_of_island ( mut grid : Vec < Vec < i32 >> ) -> i32 {
let m = grid . len ();
let n = grid [ 0 ]. len ();
let mut res = 0 ;
for i in 0 .. m {
for j in 0 .. n {
res = res . max ( Self :: dfs ( & mut grid , i , j ));
}
}
res
}
}