Number of Islands

BFS method

1. Loop through the two-dimensional grid.
2. Once found an island, that is to say, grid[i][j] == true, islandCount++.
3. Queue in grid[i][j], mark it as false. Use BFS method to queue in and find all adjacent islands, mark all of them as false. Thus we only count once for one block of island.

public class Solution {
    /*
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */

     // we use Coordinate class to queue in the x and y coordinates
    public class Coordinate {
        int x;
        int y;
        public Coordinate (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int numIslands(boolean[][] grid) {

        int result = 0;
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return result;
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j]) {
                    // count once, then mark the whole island as 0
                    markAdjacentGrids(new Coordinate(i, j), grid); 
                    result++;
                }
            }
        }
        return result;
    }

    public void markAdjacentGrids(Coordinate point, boolean[][] grid) {
        int[] directionX = {0, 0, 1, -1};
        int[] directionY = {1, -1, 0, 0};

        Queue<Coordinate> queue = new LinkedList<>();
        queue.offer(point);
        grid[point.x][point.y] = false;

        while (!queue.isEmpty()) {
            Coordinate tmp = queue.poll();

            for (int i = 0; i < 4; i++) {
                int x = tmp.x + directionX[i];
                int y = tmp.y + directionY[i];

                if (!inBoundary(x, y, grid)) {
                    continue;
                }

                if (grid[x][y]) {
                    queue.offer(new Coordinate(x, y));
                    grid[x][y] = false;
                }
            }
        }
    }

    public boolean inBoundary(int x, int y, boolean[][] grid) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
            return false;
        }
        return true;
    }
}

Union Find Method

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

Elements in the same subset will finally point to the same parent element.

If the root elements of two elements are different, then these two elements belong to two different subsets.

For example, int[] parent = {0, 1, 2, 3, 4, 5}

       index   0   1   2   3   4 

       value   0   1   2   3   4

There are five subsets since parent[i] == i, each dataset element's parent is pointing to itself.

       index   0   1   2   3   4

       value   1   1   2   3   4

If we make parent[0] = 1, then 0 -> 1, 0 and 1 has the same parent element 1, so 0 and 1 belong to the same subset.

      index    0   1   2   3   4

      value    1   2   2   3   4

If we make parent[1] = 2, then 1 -> 2, 0 -> 1 -> 2, so 0, 1, 2 have the same root parent element 2, so they belong to the same subset.

Solution with Union Find

1. Convert m * n (m rows, n columns) matrix (grid[][]) to a one-dimensional array (parent[]) with length of m*n. For each grid[i][j], match (i, j) to (n * i + j). So index (n * i + j) represents the grid[i][j], parent[n * i + j] represents which subset the grid[i][j] is belonging to.
2. Count all islands (int count).
3. Loop through the grid, if find an island X (points to root parent element S), check adjacent cells. Any adjacent island should be in the same subset of X. If there is an adjacent island Y and it is not in the same subset of X, that is to say, the root parent element of Y is not S, then merge Y to subset S by setting Y as the parent element of S, count--.
4. As long as one island is merge to a subset, the number of island will decrement 1. After we unite all the connected islands, we get the number of island.

class UnionFind {
    private int[] parent;
    private int count;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        count = 0;
    }

    public int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    public void connect(int x, int y) {
        int subsetx = find(x);
        int subsety = find(y);

        if (subsetx != subsety) {
            parent[subsetx] = subsety;
            count--;
        }
    }

    public void setCount(int num) {
        count = num;
    }

    public int count() {
        return count;
    }
}

public class Solution {
    /*
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */

    public int numIslands(boolean[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int count = 0;
        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]) {
                    count++;
                }
            }
        }

        UnionFind uf = new UnionFind(m * n);
        uf.setCount(count);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {

                    if (i > 0 && grid[i - 1][j]) {
                        uf.connect(n * i + j, n * (i - 1) + j);
                    }

                    if (i < m - 1 && grid[i + 1][j]) {
                        uf.connect(n * i + j, n * (i + 1) + j);
                    }

                    if (j > 0 && grid[i][j - 1]) {
                        uf.connect(n * i + j, n * i + j - 1);
                    }

                    if (j < n - 1 && grid[i][j + 1]) {
                        uf.connect(n * i + j, n * i + j + 1);
                    }
                }
            }
        }

        return uf.count();
    }
}