Number of Islands II

This page explains Java solution to problem Number of Islands II using Union Find algorithm.

Problem Statement

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class NumberOfIslandsIi {
    private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();

        int[] rootArr = new int[m * n];
        int count = 0;
        Arrays.fill(rootArr, -1);
        for(int[] position: positions) {
            int x = position[0];
            int y = position[1];
            int root = x * n + y;
            if(rootArr[root] == -1) {
                count++;
                rootArr[root] = root;
                for(int[] dir: dirs) {
                    int xNew = x + dir[0];
                    int yNew = y + dir[1];
                    int rootNeighbour = xNew * n + yNew;
                    if(xNew >= 0 && xNew < m && yNew >= 0 && yNew < n && rootArr[rootNeighbour] != -1) {
                        rootNeighbour = find(rootArr, rootNeighbour);
                        if(rootArr[root] != rootNeighbour) {
                            count--;
                            rootArr[rootNeighbour] = root;
                        }
                    }
                }
            }
            res.add(count);
        }
        return res;
    }

    private int find(int[] rootArr, int root) {
        if(rootArr[root] == root) return root;
        else return find(rootArr, rootArr[root]);
    }
}

Time Complexity

O(K * log(M * N) Where
K is total number of positions to process
M is number of rows
N is number of cols

Space Complexity

O(M * N) Where
M is number of rows
N is number of cols