305. Number of Islands II

/**
 * Using Union Find with ranks and path compression.
 *
 * Time Complexity: O(M*N + P). M*N to fill the arrays with -1. This can be
 * minimized by increasing the parents and ranks array by 1. (Check solution
 * below)
 *
 * Space Complexity: O(M*N)
 *
 * M = Number of rows, N = Number of columns, P = number of positions.
 */
class Solution {
    class UnionFind {
        int count;
        int[] parents;
        int[] ranks;

        UnionFind(int m, int n) {
            count = 0;
            parents = new int[m * n];
            ranks = new int[m * n];
            Arrays.fill(parents, -1);
        }

        int findRoot(int pos) {
            if (pos != parents[pos]) {
                parents[pos] = findRoot(parents[pos]);
            }
            return parents[pos];
        }

        boolean isValidIsland(int pos) {
            return parents[pos] >= 0;
        }

        void setParent(int pos) {
            parents[pos] = pos;
            count++;
        }

        void union(int x, int y) {
            int pX = findRoot(x);
            int pY = findRoot(y);

            if (pX == pY) {
                return;
            }

            if (ranks[pX] >= ranks[pY]) {
                parents[pY] = pX;
                ranks[pX] = ranks[pX] == ranks[pY] ? ranks[pX] + 1 : ranks[pX];
            } else {
                parents[pX] = pY;
            }
            count--;
        }
    }

    private static final int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList();
        if (positions == null || positions.length == 0 || m <= 0 || n <= 0) {
            return result;
        }

        UnionFind uf = new UnionFind(m, n);

        for (int[] pos : positions) {
            int curPos = pos[0] * n + pos[1];
            uf.setParent(curPos);

            for (int[] dir : dirs) {
                int x = pos[0] + dir[0];
                int y = pos[1] + dir[1];
                int nextPos = x * n + y;
                if (x < 0 || y < 0 || x > m - 1 || y > n - 1 || !uf.isValidIsland(nextPos)) {
                    continue;
                }
                uf.union(curPos, nextPos);
            }

            result.add(uf.count);
        }

        return result;
    }
}

/**
 * Using Union Find with ranks and path compression.
 *
 * Time Complexity: O(P)
 *
 * Space Complexity: O(M*N)
 *
 * M = Number of rows, N = Number of columns, P = number of positions.
 */
class Solution {
    class UnionFind {
        int count;
        int[] parents;
        int[] ranks;

        UnionFind(int m, int n) {
            count = 0;
            parents = new int[m * n + 1];
            ranks = new int[m * n + 1];
        }

        int findRoot(int pos) {
            if (pos != parents[pos]) {
                parents[pos] = findRoot(parents[pos]);
            }
            return parents[pos];
        }

        boolean isValidIsland(int pos) {
            return parents[pos] > 0;
        }

        void setParent(int pos) {
            parents[pos] = pos;
            count++;
        }

        void union(int x, int y) {
            int pX = findRoot(x);
            int pY = findRoot(y);

            if (pX == pY) {
                return;
            }

            if (ranks[pX] >= ranks[pY]) {
                parents[pY] = pX;
                ranks[pX] = ranks[pX] == ranks[pY] ? ranks[pX] + 1 : ranks[pX];
            } else {
                parents[pX] = pY;
            }
            count--;
        }
    }

    private static final int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList();
        if (positions == null || positions.length == 0 || m <= 0 || n <= 0) {
            return result;
        }

        UnionFind uf = new UnionFind(m, n);

        for (int[] pos : positions) {
            int curPos = pos[0] * n + pos[1] + 1;
            uf.setParent(curPos);

            for (int[] dir : dirs) {
                int x = pos[0] + dir[0];
                int y = pos[1] + dir[1];
                int nextPos = x * n + y + 1;
                if (x < 0 || y < 0 || x > m - 1 || y > n - 1 || !uf.isValidIsland(nextPos)) {
                    continue;
                }
                uf.union(curPos, nextPos);
            }

            result.add(uf.count);
        }

        return result;
    }
}