## 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[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);

}

}