# LeetCode 200. Number of Islands

## 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.length`
• `n == grid[i].length`
• `1 <= m, n <= 300`
• `grid[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)):
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) - 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).

## 3 Thoughts to “LeetCode 200. Number of Islands”

1. Vivkey says:

class Solution {
public int numIslands(char[][] grid) {
if(grid == null || grid.length ==0 || grid.length ==0) return 0;
int count =0;
int m = grid.length;
int n = grid.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.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);

}
}