Find the no. of Islands

The problem, simply

You get a map as a grid of m rows and n columns. Each square is '1' for land or '0' for water. Land squares that touch up, down, left or right belong to the same island. Touching only at a corner does not count.

Return how many islands there are.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a separate "seen" grid, so you never change the map. When you find land you have not seen, count it and use a waiting line to visit its whole island.

1. Make a seen grid of the same size, all false.
2. Scan every square. If it is land and not seen, add 1 to the count.
3. Put it in a waiting line, mark it seen, and spread: for each square you take out, add its land neighbors that are not seen yet.

class IslandsBfs {
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length, count = 0;
        boolean[][] seen = new boolean[m][n];
        int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != '1' || seen[r][c]) continue;
                count++;                                    // a brand new island
                Deque<int[]> line = new ArrayDeque<>();
                line.add(new int[]{r, c});
                seen[r][c] = true;
                while (!line.isEmpty()) {
                    int[] cell = line.poll();
                    for (int[] s : steps) {
                        int nr = cell[0] + s[0], nc = cell[1] + s[1];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1' && !seen[nr][nc]) {
                            seen[nr][nc] = true;            // mark when it joins the line
                            line.add(new int[]{nr, nc});
                        }
                    }
                }
            }
        }
        return count;
    }
}

How long it takes: every square is scanned once and joins the line at most once, O(m * n). Extra room: the seen grid is O(m * n), plus the line.

Way 2: the clever way

Skip the extra grid. Turn land into water as you visit it, the bucket of water from the story. A sunk square can never be counted twice, and the depth first recursion is very short to write.

1. Scan every square.
2. When you find a '1', add 1 to the count and call sink on it.
3. sink(r, c): if the square is off the map or is water, stop. Otherwise set it to '0' and call sink on the four neighbors.

class IslandsSink {
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int count = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    count++;                                // new island found
                    sink(grid, r, c);                       // flood it so it is never counted again
                }
            }
        }
        return count;
    }

    static void sink(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return;
        grid[r][c] = '0';
        sink(grid, r - 1, c);   // up
        sink(grid, r + 1, c);   // down
        sink(grid, r, c - 1);   // left
        sink(grid, r, c + 1);   // right
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };
        System.out.println(numIslands(grid));   // 3
    }
}

How long it takes: each square is turned to water at most once and looked at a few times, O(m * n). Extra room: no seen grid, but the recursion can go as deep as the biggest island. If the whole map is land, that is O(m * n) calls.

Watch out for

• The grid holds characters '1' and '0', not numbers 1 and 0. Comparing with 1 is always false.
• Sinking changes the input. If the caller still needs the map, copy it first or use the seen grid.
• A 1000 by 1000 map that is all land makes the recursion a million calls deep and can overflow the stack. Use BFS or your own stack there.
• Check the bounds before reading grid[r][c].

What interviewers ask next

• Corners count too: use 8 directions instead of 4.
• Size of the biggest island: make sink return how many squares it sank, and keep the max.
• Islands appear one at a time (Number of Islands II): use union find. Each new land square starts its own group, then joins with land neighbors; count groups as you go.
• Count distinct island shapes: record the path of moves during each sink, like "down, right, up", and put the strings in a set.
• Closed islands or enclaves: first sink every island that touches the border, then count what is left.

Remember this

Grown-up words: the map is a grid graph where each square is a vertex and touching squares share an edge, an island is a connected component, flooding is depth first search (or breadth first search with a queue), and sinking is marking visited in place.