Easiest Java Solution with Explanations


  • 171

    This is a basic union-find problem. Given a graph with points being added, we can at least solve:

    1. How many islands in total?
    2. Which island is pointA belonging to?
    3. Are pointA and pointB connected?

    The idea is simple. To represent a list of islands, we use trees. i.e., a list of roots. This helps us find the identifier of an island faster. If roots[c] = p means the parent of node c is p, we can climb up the parent chain to find out the identifier of an island, i.e., which island this point belongs to:

    Do root[root[roots[c]]]... until root[c] == c;
    

    To transform the two dimension problem into the classic UF, perform a linear mapping:

    int id = n * x + y;
    

    Initially assume every cell are in non-island set {-1}. When point A is added, we create a new root, i.e., a new island. Then, check if any of its 4 neighbors belong to the same island. If not, union the neighbor by setting the root to be the same. Remember to skip non-island cells.

    UNION operation is only changing the root parent so the running time is O(1).

    FIND operation is proportional to the depth of the tree. If N is the number of points added, the average running time is O(logN), and a sequence of 4N operations take O(NlogN). If there is no balancing, the worse case could be O(N^2).

    Remember that one island could have different roots[node] value for each node. Because roots[node] is the parent of the node, not the highest root of the island. To find the actually root, we have to climb up the tree by calling findIsland function.

    Here I've attached my solution. There can be at least two improvements: union by rank & path compression. However I suggest first finish the basis, then discuss the improvements.

    Cheers!

    int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList<>();
        if(m <= 0 || n <= 0) return result;
    
        int count = 0;                      // number of islands
        int[] roots = new int[m * n];       // one island = one tree
        Arrays.fill(roots, -1);            
    
        for(int[] p : positions) {
            int root = n * p[0] + p[1];     // assume new point is isolated island
            roots[root] = root;             // add new island
            count++;
    
            for(int[] dir : dirs) {
                int x = p[0] + dir[0]; 
                int y = p[1] + dir[1];
                int nb = n * x + y;
                if(x < 0 || x >= m || y < 0 || y >= n || roots[nb] == -1) continue;
                
                int rootNb = findIsland(roots, nb);
                if(root != rootNb) {        // if neighbor is in another island
                    roots[root] = rootNb;   // union two islands 
                    root = rootNb;          // current tree root = joined tree root
                    count--;               
                }
            }
    
            result.add(count);
        }
        return result;
    }
    
    public int findIsland(int[] roots, int id) {
        while(id != roots[id]) id = roots[id];
        return id;
    }
    

    Path Compression (Bonus)


    If you have time, add one line to shorten the tree. The new runtime becomes: 19ms (95.94%).

    public int findIsland(int[] roots, int id) {
        while(id != roots[id]) {
            roots[id] = roots[roots[id]];   // only one line added
            id = roots[id];
        }
        return id;
    }

  • 1

    I find it confusing to see m and n in the runtime analysis with m meaning something different than the parameter m and n not being defined at all (so is it the parameter n?).


  • 1

    Hi Stefan, thanks for pointing out. I've updated the parameter names to be N :)


  • 2
    J
        int rootNb = findIsland(roots, idNb);
        root = findIsland(roots, root);
        if(root != rootNb) {        // if neighbor is in another island
            roots[root] = rootNb;   // union two islands 
            count--;               
        }
    

    This will make your program much faster, since before this it could easily make depth very large.


  • 1

    Thanks for your comment! I tested, and the run time is even slower with the line added. So I doubt the use of it. I think for each point being added, we already got the root, which only need to compare at most 4 neighbors.


  • 0
    J

    But when I ran your code it's more than 130ms.


  • 1
    J

    They are adding new cases. So think of a case when new islands keep added at (0,0), (0,1)...(0,n), your code will make the tree a straight line.


  • 0

    Hmm. Yeah it looks like the new test cases would take more time to run. Yeah but by adding this line makes the running time almost the same. Need to dig into it. Thanks!


  • 0
    J

    You didn't see changes in this line roots[root] = rootNb;


  • 1

    Thanks a lot:) Will verify your suggestion.


  • 2
    D

    very impressive to come out this solution in 15min. awesome!


  • 0
    V

    when you use roots[root]=rootNb; if the new node is connected two existed islands, it will be updated twice and it won't make the three joined as one, is it the case?


  • 0
    J

    So I have this root = findIsland(roots, root); to make sure not make this situation happen.


  • 0
    V

    oh, i missed this line, sorry. that will work, i prefer the neighbours to converge to the new node though, just personal preference.


  • 0
    C

    path compression

    public int findIsland(int[] roots, int id, int finalId) {
            while(id != roots[id]){
                int temp = id;
                id = roots[id];
                roots[temp] = finalId;
            } 
            return id;
       }

  • 1
    J

    How to call this findIsland? Specifically, what should the finalId be?


  • 1
    C

    Same as the original post


  • 1
    G

    Hi yavinci, thanks for sharing this elegant solution. I have a question about the union operation: in the if(root != rootNb) { roots[rootNb] = root; count--;} clause it seems that all the elements in the rootNB island change their value and go with the root. While it seems to me that this operation will only change the neighbor's value, not the entire island's. Can you help me find why?


  • 1

    @GuaGua1991 notice that root[rootNb] = root actually means parent not highest root. It's setting the new node to be the parent of the old neighbor. UNION is only changing one parent to be the other, instead of changing all the nodes in the islands, so it's O(1). The nodes in one island can have different root value, but same root[root[root[...]]] value.


  • 1

    @Jinx_boom You are right. I've updated my solution. With more test cases added, I realized that joining current root with neighbor's root is making tree shorter, since current node is starting with height 1. It's is always shorter than neighbor's height.


Log in to reply
 

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