Long but clear java solution beats 100%


  • 0
    Y

    Union Find. An important optimization is to minimize the height of the tree by asking leaves to point to root directly.

    public class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList<>();
        int count = 0;
        int[] parent = new int[m * n]; // use an array to represent the tree
        for (int i = 0; i < m * n; i++) parent[i] = -1; // indicate this position is 0
        for (int[] point : positions) {
            count++;
            int key = point[0] * n + point[1]; // map (row, col) to a single value
            parent[key] = key; // set itself as root
            if (key - n >= 0) { // can go up
                int next = key - n;
                if (parent[next] >= 0) {
                    while (parent[next] != next) { // find the root of the neighbor
                        int copy = parent[next];
                        parent[next] = key; // important for efficiency
                        next = copy;
                    }
                    parent[next] = key; // set the neighbor's root
                    count--;
                }
            }
            if (key + n < m * n) { // can go down
                int next = key + n;
                if (parent[next] >= 0) {
                    while (parent[next] != next) {
                        int copy = parent[next];
                        parent[next] = key;
                        next = copy;
                    }
                    if (key != next) {
                        count--;
                        parent[next] = key;
                    }
                }
            }
            if (key % n > 0) { // can go left
                int next = key - 1;
                if (parent[next] >= 0) {
                    while (parent[next] != next) {
                        int copy = parent[next];
                        parent[next] = key;
                        next = copy;
                    }
                    if (key != next) {
                        count--;
                        parent[next] = key;
                    }
                }
            }
            if (key % n < n - 1) { // can go right
                int next = key + 1;
                if (parent[next] >= 0) {
                    while (parent[next] != next) {
                        int copy = parent[next];
                        parent[next] = key;
                        next = copy;
                    }
                    if (key != next) {
                        count--;
                        parent[next] = key;
                    }
                }
            }
            result.add(count);
        }
        return result;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.