Number of Islands

Question (LC.200)

Given a 2D grid consists of "1"s and "0"s, count the number of connected "1"s.

An island ("1"s) can be connected vertically and horizontally. Assume all 4 edges are surrounded by water.

Example

The given input is a char[][].

11110
11010
11000
00000

Output: 1

11000
11000
00100
00011

Output: 1+1+1 = 3

Analysis

We can do either BFS or DFS. We want to eat a hamburger. We can eat normally by taking bites around the side until we finish it. Or if we want to be more savage, we can keep biting until on direction is finished then comeback start another direction until we finish the hamburger.

BFS Approach

Preliminaries

class Pos {
    int x, y;
    Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

static final int[] DX = {-1, 0, 1, 0};
static final int[] DY = {0, 1, 0, -1};

Main function - we want to destroy an island when detect it

public int numIslands(char[][] grid) {
    int islands = 0;
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return islands;
    }
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                bfsDestroy(grid, i, j);
                islands++;
            }
        }
    }
    return islands;
}

BFS - destroy the island

private void bfsDestroy(char[][] grid, int i, int j) {
    Queue<Pos> queue = new LinkedList<>();
    queue.offer(new Pos(i, j));
    grid[i][j] = '0';

    while (!queue.isEmpty()) {
        Pos current = queue.poll();
        // for each neighbor
        for (int n = 0; n < 4; n++) {
            Pos neighbor = new Pos(current.x + DX[n], current.y + DY[n]);
            if (!inGrid(grid, neighbor)) {
                continue;
            }
            if (grid[neighbor.x][neighbor.y] == '1') {
                queue.offer(neighbor);
                grid[neighbor.x][neighbor.y] = '0';
            }
        }
    }
}

Check Boundary

private boolean inGrid(char[][] grid, Pos pt) {
    int m = grid.length;
    int n = grid[0].length;
    return pt.x >= 0 && pt.x < m && pt.y >= 0 && pt.y < n;
}

Time Complexity

O(mn)

DFS Approach

private void dfsDestroy(char[][] grid, Pos pt) {
    if (!inGrid(grid, pt)) {
        return;
    }
    if (grid[pt.x][pt.y] == '1') {
        grid[pt.x][pt.y] = '0';
        for (int n = 0; n < 4; n++) {
            Pos neighbor = new Pos(pt.x + DX[n], pt.y + DY[n]);
            dfsDestroy(grid, neighbor);
        }
    }
}

Follow Up #0

Only destroy the island if the number of 1s is less than k

• have a flag at the end of the path, if path_length < k, give permission to destroy the island on the back back (backtracking) otherwise label it as red zone (label is -1 or something so we don't touch it). So we want to measure how long this subway is before we eat it backward. i.e. if it's 12in we don't want to eat it, label it red. But if it's 6in, then eat it backward.

Follow Up #1

Count number of lakes

Follow up #2

Measure the length of the seashore

Number of Islands II (Union Find)

Reference

Segmentfault Number of Islands by Ethan Li