Finding The Number of Islands

Problem Statement

Given a matrix of size M x N, where ‘1’ represents land, while ‘0’ represents water. The task is to return the number of islands present in the matrix. An island is a group of 1’s surrounded either vertically or horizontally.

Examples:

Input:

Output: 3
Explanation: Shown in image

Approach 1: DFS

The idea is to consider the given matrix as a graph, where each cell is a node of the given graph. Two nodes contain an edge if and only if there is a ‘1’ either horizontally or vertically.

Algorithm

• Scan the matrix from (0,0) till (N, M).
• If the current element is ‘1’, start a DFS.
• In the DFS traversal, mark every visited node.
• Count the number of islands as the number nodes that trigger the DFS.
• Return count.

C++ Implementation

```void dfs(vector &lt; vector &lt; char >> &amp; grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();

grid[r][c] = '0';
if (r - 1 >= 0 &amp;&amp; grid[r - 1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 &lt; nr &amp;&amp; grid[r + 1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 &amp;&amp; grid[r][c - 1] == '1') dfs(grid, r, c - 1);
if (c + 1 &lt; nc &amp;&amp; grid[r][c + 1] == '1') dfs(grid, r, c + 1);
}

int numIslands(vector &lt; vector &lt; char >> &amp; grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();

int num_islands = 0;
for (int r = 0; r &lt; nr; ++r) {
for (int c = 0; c &lt; nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}

return num_islands;
}```

Java Implementation

``` void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;

if (r &lt; 0 || c &lt; 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}

grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r &lt; nr; ++r) {
for (int c = 0; c &lt; nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}

return num_islands;
}```

Python Implementation

```def numIslands(self, grid):
if not grid:
return 0

count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
self.dfs(grid, i, j)
count += 1
return count

def dfs(self, grid, i, j):
if i &lt; 0 or j &lt; 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != "1":
return
grid[i][j] = "#"
self.dfs(grid, i + 1, j)
self.dfs(grid, i - 1, j)
self.dfs(grid, i, j + 1)
self.dfs(grid, i, j - 1)```

Time Complexity:O(M * N), where M and N is the size of the matrix
Space Complexity:O(M * N).

Approach 2: BFS

The problem can also be solved using the BFS approach. The logic remains the same as the previous approach.

Algorithm

• Scan the matrix from (0,0) till (N, M).
• If the current element is ‘1’, start a BFS.
• Consider a queue and put the current node into the queue.
• Iteratively visit its neighbours vertically and horizontally and mark them as visited.
• The count is the total number of times the BFS has been invoked.
• Return count.

C++ Code

```int numIslands(vector &lt; vector &lt; char >> &amp; grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();

int num_islands = 0;
for (int r = 0; r &lt; nr; ++r) {
for (int c = 0; c &lt; nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0'; // mark as visited
queue &lt; pair &lt; int, int >> neighbors;
neighbors.push({
r,
c
});
while (!neighbors.empty()) {
auto rc = neighbors.front();
neighbors.pop();
int row = rc.first, col = rc.second;
if (row - 1 >= 0 &amp;&amp; grid

== '1') {
neighbors.push({
row - 1,
col
});
grid

= '0';
}
if (row + 1 &lt; nr &amp;&amp; grid

== '1') {
neighbors.push({
row + 1,
col
});
grid

= '0';
}
if (col - 1 >= 0 &amp;&amp; grid

== '1') {
neighbors.push({
row,
col - 1
});
grid

= '0';
}
if (col + 1 &lt; nc &amp;&amp; grid

== '1') {
neighbors.push({
row,
col + 1
});
grid

= '0';
}
}
}
}
}

return num_islands;```

Java Code

```public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;

for (int r = 0; r &lt; nr; ++r) {
for (int c = 0; c &lt; nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0'; // mark as visited
Queue &lt; Integer > neighbors = new LinkedList &lt; > ();
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 &amp;&amp; grid

== '1') {
neighbors.add((row - 1) * nc + col);
grid

= '0';
}
if (row + 1 &lt; nr &amp;&amp; grid

== '1') {
neighbors.add((row + 1) * nc + col);
grid

= '0';
}
if (col - 1 >= 0 &amp;&amp; grid

== '1') {
neighbors.add(row * nc + col - 1);
grid

= '0';
}
if (col + 1 &lt; nc &amp;&amp; grid

== '1') {
neighbors.add(row * nc + col + 1);
grid

= '0';
}
}
}
}
}

return num_islands;
}```

Python Code

```from collections import deque

def numIslands(grid):
if not grid:
return 0
lands = set(
[
(i, j)
for j in xrange(len(grid[0]))
for i in xrange(len(grid))
if grid[i][j] == "1"
]
)
count = 0
while lands:
count += 1
i, j = lands.pop()
connected = deque()
connected.append((i, j))
while connected:
i, j = connected.popleft()
if (i + 1, j) in lands:
connected.append((i + 1, j))
lands.remove((i + 1, j))
if (i - 1, j) in lands:
connected.append((i - 1, j))
lands.remove((i - 1, j))
if (i, j + 1) in lands:
connected.append((i, j + 1))
lands.remove((i, j + 1))
if (i, j - 1) in lands:
connected.append((i, j - 1))
lands.remove((i, j - 1))
return count```

Time Complexity:O(M * N), where M and N is the size of the matrix
Space Complexity:O(min(M,N)).

Practice Question

Commutable Islands

FAQs

What is the time and space complexity of the DFS approach?
The time and space complexity of the DFS  approach is O(M * N) and O(M * N).

In terms of space complexity, is the BFS approach efficient over DFS?
Yes, the space complexity for the BFS approach is O(min(N,M)), in the worst case when the grid is filled completely with 1’s, whereas for DFS it is O(N*M).