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

This question is essentially searching connected components in a simple graph. We can solve it with either BFS or DFS. We prefer BFS over DFS because 1 1 1 1 1 ... 1 can overflow the call stack. Say we want to eat a hamburger. Do you want to eat normally by taking a couple bites around the side? Or do you want to keep biting in one direction until you reach the end of that direction? Sure both methods can finish the burger, but your mouth might get very full by choosing the second way.

BFS Approach

for the graph
    if 1 then bfsConnected
bfsConnected
    if inBound and 1 offer to queue
    no need visited b/c we can change the grid

BFS Code

private class Pos {
    int row;
    int col;
    public Pos(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

int[] drow = new int[] {0, -1, 0, 1};
int[] dcol = new int[] {-1, 0, 1, 0};

private boolean inBound(char[][] grid, Pos pt) {
    int m = grid.length;
    int n = grid[0].length;
    if (pt.row < 0 || pt.row >= m) {
        return false;
    }
    if (pt.col < 0 || pt.col >= n) {
        return false;
    }
    return true;
}

public int numIslands(char[][] grid) {
    int landCount = 0;
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return landCount;
    }
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                landCount++;
                bfsConnected(grid, new Pos(i,j));
            }
        }
    }
    return landCount;
}

private void bfsConnected(char[][] grid, Pos start) {
    // init queue
    Queue<Pos> queue = new LinkedList<>();
    queue.offer(start);
    grid[start.row][start.col] = '0';
    // bfs
    Pos current;
    while (!queue.isEmpty()) {
        current = queue.poll();
        // search its neighbors
        for (int p = 0; p < 4; p++) {
            Pos neighbor = new Pos(current.row + drow[p], current.col + dcol[p]);
            if (!inBound(grid, neighbor)) {
                continue;
            }
            if (grid[neighbor.row][neighbor.col] == '1') {
                queue.offer(neighbor);
                grid[neighbor.row][neighbor.col] = '0'; // visited
            }
        }  
    }
}

Time Complexity

O(mn)

DFS Approach

private void dfsConnected(char[][] grid, Pos current) {
    // base
    if (!inBound(grid, current)) {
        return;
    }
    if (grid[current.row][current.col] == '0') {
        return;
    }
    // previsit
    grid[current.row][current.col] = '0'; // visited
    // dfs
    for (int p = 0; p < 4; p++) {
        Pos neighbor = new Pos(current.row + drow[p], current.col + dcol[p]);
        dfsConnected(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