Finding The Number of Islands

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 < vector < char >> & grid, int r, int c) {
  int nr = grid.size();
  int nc = grid[0].size();
 
  grid[r][c] = '0';
  if (r - 1 >= 0 && grid[r - 1][c] == '1') dfs(grid, r - 1, c);
  if (r + 1 < nr && grid[r + 1][c] == '1') dfs(grid, r + 1, c);
  if (c - 1 >= 0 && grid[r][c - 1] == '1') dfs(grid, r, c - 1);
  if (c + 1 < nc && grid[r][c + 1] == '1') dfs(grid, r, c + 1);
}
 
int numIslands(vector < vector < char >> & grid) {
  int nr = grid.size();
  if (!nr) return 0;
  int nc = grid[0].size();
 
  int num_islands = 0;
  for (int r = 0; r < nr; ++r) {
    for (int c = 0; c < 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 < 0 || c < 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 < nr; ++r) {
    for (int c = 0; c < 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 < 0 or j < 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 < vector < char >> & grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();
 
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          queue < pair < 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 && grid			
== '1') { neighbors.push({ row - 1, col }); grid
= '0'; } if (row + 1 < nr && grid
== '1') { neighbors.push({ row + 1, col }); grid
= '0'; } if (col - 1 >= 0 && grid
== '1') { neighbors.push({ row, col - 1 }); grid
= '0'; } if (col + 1 < nc && 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 < nr; ++r) {
    for (int c = 0; c < nc; ++c) {
      if (grid[r][c] == '1') {
        ++num_islands;
        grid[r][c] = '0'; // mark as visited
        Queue < Integer > neighbors = new LinkedList < > ();
        neighbors.add(r * nc + c);
        while (!neighbors.isEmpty()) {
          int id = neighbors.remove();
          int row = id / nc;
          int col = id % nc;
          if (row - 1 >= 0 && grid			
== '1') { neighbors.add((row - 1) * nc + col); grid
= '0'; } if (row + 1 < nr && grid
== '1') { neighbors.add((row + 1) * nc + col); grid
= '0'; } if (col - 1 >= 0 && grid
== '1') { neighbors.add(row * nc + col - 1); grid
= '0'; } if (col + 1 < nc && 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).

Previous Post

Interleaving Strings (C, Java, and Python Code)

Next Post

Container With Most Water

Exit mobile version