Number of Islands

Problem Statement

LeetCode-200: Given an m x n 2D binary grid grid which represents a 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.

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Approach

As with any grid problem, let’s see if we can solve this using a Depth First Search (DFS) or Breadth First Search (BFS) approach.

Using DFS, we can traverse the grid and mark the visited nodes as we go along.

1. We can start from the first cell and traverse the grid.
2. If we encounter a cell with a value of 1, we can increment the count of islands.
3. Start DFS from the current cell and mark all the connected cells as visited (i.e., change the value of the cell to 0).
4. Continue this process until we have traversed the entire grid.
5. The number of times we start the DFS (represented by the count of islands) is the answer.

Implementation

Here is a Java implementation of the above approach:

public int numIslands(char[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int count=0;
    for(int i=0; i < rows; i++){
        for(int j=0; j < cols; j++){
            if(grid[i][j] == '1'){
                count++;
                dfs(grid, rows, cols, i, j);
            }
        }
    }
    return count;
}

private final int[] dirs = new int[]{0,1,0,-1,0};
private void dfs(char[][]grid, int rows, int cols, int row, int col){
    if(row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0'){
        return;
    }
    grid[row][col] = '0';
    for(int i=0; i < 4; i++){
        int newRow = row + dirs[i];
        int newCol = col + dirs[i+1];
        dfs(grid, rows, cols, newRow, newCol);
    }
}

Complexity Analysis

Due to the recursive nature of DFS and nested for loops, for a grid with $M$ rows and $N$ columns, it has a time complexity of $O(M \times N)$ and a space complexity of $O(M \times N)$.

Follow-up

Can you solve this problem using BFS?

To solve this problem using BFS, we can use a queue to store the cells that we need to visit. We can start from the first cell and traverse the grid. If we encounter a cell with a value of 1, we can increment the count of islands and start BFS from the current cell.

1. We can start from the first cell and traverse the grid.
2. If we encounter a cell with a value of 1
   1. Increment the count of islands.
   2. Mark it visited by changing the value of the cell to 0.
   3. Start BFS from the current cell by enqueuing it.
   4. While the queue is not empty, dequeue the cell.
      1. Mark all the connected cells as visited (i.e., change the value of the cell to 0).
      2. Enqueue the connected cells.
3. The number of times we start the BFS (represented by the count of islands) is the answer.
4. Continue this process until we have traversed the entire grid.

Here is a Java implementation of the above approach:

public int numIslands(char[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int count = 0;

    Queue<int[]> queue = new LinkedList<>();
    int[] dirs = new int[] { 0, 1, 0, -1, 0 };
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                count++;
                grid[i][j] = '0';
                queue.offer(new int[] { i, j });
    
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
    
                    for (int k = 0; k < 4; k++) {
                        int newRow = cell[0] + dirs[k];
                        int newCol = cell[1] + dirs[k + 1];
                
                        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                                && grid[newRow][newCol] == '1') {
                            grid[newRow][newCol] = '0';
                            queue.offer(new int[] { newRow, newCol });
                        }
                    }
                }
            }
        }
    }
    return count;
}

The time and space complexity of the BFS approach is also $O(M \times N)$.