Share my Java Union-Find Solution


  • 3

    Union-Find is useful in finding relationship between disjoint subsets (in this case, islands), we can use this simple but amazing algorithm in detecting cycles in undirected graph (see solution here).

    For this problem, we go through each input position, first mark it as a new island, then perform union find with its neighbours that are islands.

    public class Solution {
      int[] dx = {-1, 1, 0, 0};
      int[] dy = {0, 0, -1, 1};
      
      public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();
        
        int count = 0;
        int[] nums = new int[m*n];
        Arrays.fill(nums, -1);
      
        for (int[] p : positions) {
          // for each position, mark it as new island
          int x = p[0]*n + p[1];
          nums[x] = x;
          count++;
          
          for (int i = 0; i < 4; i++) {
            // check neighbours
            int nx = p[0] + dx[i], ny = p[1] + dy[i], y = nx*n + ny;
            
            // ignore invalid position
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || nums[y] == -1) continue;
            
            // find and union islands
            y = find(nums, y);
            x = find(nums, x);
            nums[y] = x;
            
            // merge two isolated islands
            if (y != x) count--;
          }
          
          res.add(count);
        }
      
        return res;
      }
      
      int find(int nums[], int i) {
        if (nums[i] == i) return i;
        nums[i] = find(nums, nums[i]);
        return nums[i];
      }
    
    }
    

    We can also use Union by Rank to reduce the time complexity down to O(k*log(mn)).


  • 0
    M

    Hi, your code is clean to understand, thanks. I want to ask what is the time complexity for this algorithm? thanks


  • 0
    M

    Is it O(kmn)?


Log in to reply
 

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