Leetcode: Number of Islands II

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:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

Understand the problem:
https://leetcode.com/discuss/69572/easiest-java-solution-with-explanations

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. Becauseroots[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 & pass compression. However I suggest first finish the basis, then discuss the improvements.

Code (Java):

public class Solution {
    private int top;
    private int bottom;
    private int left;
    private int right;
    private int area = 0;
    
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0) {
            return 0;
        }
        
        this.top = y;
        this.bottom = y;
        this.left = x;
        this.right = x;
        
        int m = image.length;
        int n = image[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        minAreaHelper(image, x, y, visited);
        
        return area;
    }
    
    private void minAreaHelper(char[][] image, int x, int y, 
                               boolean[][] visited) {
        int m = image.length;
        int n = image[0].length;
        
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {
            return;
        }          
        
        if (image[x][y] == '0') {
            return;
        }
        
        visited[x][y] = true;
        
        // update the border 
        top = Math.min(top, y);
        bottom = Math.max(bottom, y);
        left = Math.min(left, x);
        right = Math.max(right, x);
        
        int curArea = (bottom - top + 1) * (right - left + 1);
        area = Math.max(area, curArea);
        
        minAreaHelper(image, x, y - 1, visited);
        minAreaHelper(image, x, y + 1, visited);
        minAreaHelper(image, x - 1, y, visited);
        minAreaHelper(image, x + 1, y, visited);
    }
}