Description
https://leetcode.com/problems/number-of-islands/
Given an m x n 2d grid 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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Explanation
We can use Depth First Search to solve the problem. If the grid cell is ‘1’, an island is found, we mark it to ‘0’ and continue to find all the remaining adjacent ‘1’ which belongs to the same island.
Python Solution
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] != '0':
self.helper(grid, i, j)
count += 1
return count
def helper(self, grid, i, j):
if i < 0 or i > len(grid) - 1 or j < 0 or j > len(grid[0]) - 1:
return
if grid[i][j] == '0':
return
grid[i][j] = '0'
self.helper(grid, i - 1, j)
self.helper(grid, i + 1, j)
self.helper(grid, i, j - 1)
self.helper(grid, i, j + 1)
- Time complexity: O(M * N), where M is the number of rows and N is the number of columns.
- Space complexity: O(M * N).
class Solution {
public int numIslands(char[][] grid) {
if(grid == null || grid.length ==0 || grid[0].length ==0) return 0;
int count =0;
int m = grid.length;
int n = grid[0].length;
for(int i=0; i<m; i++){
for(int j=0; j<n;j++){
if(grid[i][j] == '1'){
count++;
merge(grid,i,j);
}
}
}
return count;
}
private void merge(char[][] grid,int i,int j){
int m = grid.length;
int n = grid[0].length;
if(i=m || j=n || grid[i][j]!=’1′) return;
grid[i][j]=’X’;
merge(grid,i-1,j);
merge(grid,i+1,j);
merge(grid,i,j-1);
merge(grid,i,j+1);
}
}