Data Structures & Algorithms (Graphs): Number of Islands

Given an m x n 2-D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

NOTE: 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.

Solve Here: Leetcode 200

Intuition

Iterate over the input grid marking each cell as visited. Whenever we encounter a land cell ('1'), we treat it as a new island, increment the island count, and then use DFS or BFS to traverse all its adjacent land cells (up, down, left, right), marking them as visited. This ensures that all connected land cells are counted as part of the same island and not revisited.

public int numIslands(char[][] grid) {

  if (grid.length == 0) return 0;
  
  int islandCount = 0;
  boolean[][] visited = new boolean[grid.length][grid[0].length];
  
  for(int i = 0; i < grid.length; i++) {
    for(int j = 0; j < grid[0].length; j++) {
      if (grid[i][j] == '1' && visited[i][j] == false) {
        islandCount++;
        // dfs(grid, i, j, visited) or bfs(grid, i, j, visited)
      }
    }
  }

  return islandCount;

}

Approach 1: Depth-First Search (DFS)

Use recursion to traverse the adjacent land cells (up, down, left, right) and mark them as visited.

Hypothesis

Let F(grid, i, j, visited) be a function that marks the current cell as visited and go explore its neighbourhood (up, down, left, right) for unvisited land cells.

Recursive Steps

// 1. Mark the current node as visited
visited[i][j] = true;

// 2. Visit the neighbour at the top
dfs(grid, i-1, j, visited);
// 3. Visit the neighbour on the left
dfs(grid, i, j-1, visited);
// 4. Visit the neighbour at the bottom
dfs(grid, i+1, j, visited);
// 5. Visit the neighbour on the right
dfs(grid, i, j+1, visited);

Base Conditions

If the current cell is out of bounds or is not a land cell or is already visited, return.

if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0' || visited[i][j] == true) {
    return;
}

Visualization

Time Complexity

Since, we are visiting each cell in the grid at most twice, the overall time complexity = O(m * n).

Space Complexity

We are using a visited array of size m * n to store the visited cells. The recursive call stack can go up to a maximum depth of O(m * n) in the worst case (when all cells are land cells).

Hence, overall space complexity = O(m * n).

Approach 2: Breadth-First Search (BFS)

For each land cell ('1'), add all its adjacent land cells (up, down, left, right) to a queue and mark them as visited, potentially creating the next layer of land cells for exploration.

Algorithm

class Cell {
    int x;
    int y;

    Cell(int i, int j) {
        this.x = i;
        this.y = j;
    }
}

private boolean isInBound(int i, int j, int m, int n) {
    return i >= 0 && i < m && j >=0 && j < n; 
}

private void bfs(char[][] grid, int i, int j, boolean[][] visited) {

    Queue<Cell> queue = new LinkedList<>();
    queue.offer(new Cell(i, j));
    visited[i][j] = true;

    while (!queue.isEmpty()) {
        Cell cell = queue.poll();
        int x = cell.x;
        int y = cell.y;

        // Explore neighbour at the top
        if (isInBound(x-1, y, grid.length, grid[0].length) && grid[x-1][y] == '1' && visited[x-1][y] == false) {
            queue.offer(new Cell(x-1, y));
            visited[x-1][y] = true;
        }
        // Explore neighbour on the left
        if (isInBound(x, y-1, grid.length, grid[0].length) && grid[x][y-1] == '1' && visited[x][y-1] == false) {
            queue.offer(new Cell(x, y-1));
            visited[x][y-1] = true;
        }

        // Explore neighbour at the bottom
        if (isInBound(x+1, y, grid.length, grid[0].length) && grid[x+1][y] == '1' && visited[x+1][y] == false) {
            queue.offer(new Cell(x+1, y));
            visited[x+1][y] = true;
        }

        // Explore neighbout on the right
        if (isInBound(x, y+1, grid.length, grid[0].length) && grid[x][y+1] == '1' && visited[x][y+1] == false) {
            queue.offer(new Cell(x, y+1));
            visited[x][y+1] = true;
        }

    }

}

Visualization

Time Complexity

Since, we are visiting each cell in the grid at most twice, the overall time complexity = O(m * n).

Space Complexity

In a grid completely filled with land, the maximum number of cells in the queue at any given time is bounded by the smaller dimension of the grid, i.e., min(m, n).

Additionally, we are using a visited array of size m * n to store the visited cells. Therefore, the overall space complexity = O(min(m, n)) + O(m * n) ~ O(m * n).