200. Number of Islands

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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Solution:

Method 1: DFS

Go through the grid. If we find a '1', use DFS to find all connected '1's and set them to '0'. And increase the number of islands by 1.

Since all points in this island are set to '0' after traversal. We will not check these points any more.

Each point in the grid is checked exactly twice (one from for loop and one from dfs). The time complexity is O(mn) where m and n are the dimension of the grid.



Code:

public class Solution {
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        if (grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int islands = 0;
        
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    islands++;
                }
            }
        }
        
        return islands;
    }
    
    public void dfs(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || 
            y < 0 || y >= grid[0].length || 
            grid[x][y] == '0') {
            
            return;
        }
        grid[x][y] = '0';
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }
}

Method 2: BFS

Time complexity is O(n) and space complexity is O(n).



Code:

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        if (grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int islands = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    islands++;
                }
            }
        }
        return islands;
    }
    public void bfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i * n + j);
        HashSet<Integer> set = new HashSet<>();
        set.add(i * n + j);
        while (!queue.isEmpty()) {
            int coordinate = queue.poll();
            int x = coordinate / n;
            int y = coordinate % n;
            grid[x][y] = '0';
            int[] k = new int[] {1, 0, -1, 0, 1};
            for (int p = 0; p < 4; p++) {
                int newx = x + k[p];
                int newy = y + k[p + 1];
                if (!set.contains(newx * n + newy)) {
                    if (newx >= 0 && newx < m && newy >= 0 && newy < n) {
                        if (grid[newx][newy] == '1') {
                            queue.offer(newx * n + newy);
                            set.add(newx * n + newy);
                        }
                    }
                }
            }
        }
    }
}

Method 3: Union-Find