# Number of Islands Solution (Leetcode 200) - Top Google Coding Interview Question

*Number of Islands problem is one of the must learn interview questions to learn*

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'`

.

Solution:

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

/**
* Time Complexity: O(mn)
* Space Complexity: O(mn)
*/
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i =0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == '1') {
count++;
dfs(grid, i , j);
}
}
}
return count;
}
private void dfs(char[][] grid , int i, int j) {
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}
}