Number of Islands

MEDIUM

Given a 2d grid map of '1's (land) and '0's (water), count 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:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: 3

Algorithm

Linear scan the 2D grid map, if a node contains a ‘1’, then it is a root node that triggers a Depth First Search. During DFS, every visited node should be set as ‘0’ to mark as a visited node. Count the number of root nodes that trigger DFS, this number would be the number of islands since each DFS starting at some root identifies an island.

Consider the following figure to have a better understanding of the algorithm.

The implementation of the algorithm:

class NumberOfIsland {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int height = grid.length;
        int width = grid[0].length;
        int no = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == '1') {
                    no++;
                    DFS(grid, i, j);
                }
            }
        }
        return no;
    }

    private void DFS(char[][] grid, int i, int j) {
        int height = grid.length;
        int width = grid[0].length;
        if (i < 0 || j < 0 || i >= height || j >= width || 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));
    }
}

public class NumberOfIslandSolution {
    public static void main(String[] args) {
        char[][] matrix = {{'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}};
        NumberOfIsland solution = new NumberOfIsland();
        System.out.println("Number of Island: " + solution.numIslands(matrix));
    }
}

Complexity Analysis

  • Time Complexity: O(M×N) where M is the number of rows and N is the number of columns.
  • Space Complexity: Worst-case O(M×N) in case that the grid map is filled with lands where DFS goes by M ×N deep.

Categories: DFS

Tagged as: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s