Question

Formatted question description: https://leetcode.ca/all/305.html

305. Number of Islands II

Level

Hard

Description

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:

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

Output: [1,1,2,3]

Explanation:

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

Follow up:

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

Algorithm

Union Find.

Code

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Number_of_Islands_II {

    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

        // roots[c] = p means the parent of node c is p
        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) { // probe 4 directions
                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;
    }
}

Algorithm - 2

Each time a position is visited, first check whether the position is already a land cell. If so, add the current number of islands to the result list, and continue with the next position. Otherwise, check whether the position is adjacent to at least one land cell. If there is no adjacent land cell, then a new island is added, so add a greater island number to the result list, and update the new land cell with a new island number. Otherwise, find the minimum island number that is adjacent to the new land cell, do breadth first search on all cells adjacent to the new land cell, and update all reachable cells with the smallest island number. The number of islands may remain unchanged or decrease, and add the updated number of islands to the result list.

Finally, return the result list.

class Solution {
    Set<Integer> set = new HashSet<Integer>();

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[][] grid = new int[m][n];
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        int length = positions.length;
        List<Integer> islands = new ArrayList<Integer>();
        int islandsCount = 0;
        for (int i = 0; i < length; i++) {
            int[] position = positions[i];
            int row = position[0], column = position[1];
            if (grid[row][column] != 0) {
                islands.add(set.size());
                continue;
            }
            int minAdjacent = Integer.MAX_VALUE;
            for (int[] direction : directions) {
                int newRow = row + direction[0], newColumn = column + direction[1];
                if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n && grid[newRow][newColumn] != 0)
                    minAdjacent = Math.min(minAdjacent, grid[newRow][newColumn]);
            }
            if (minAdjacent == Integer.MAX_VALUE) {
                set.add(islandsCount + 1);
                islandsCount++;
                grid[row][column] = islandsCount;
            } else {
                grid[row][column] = minAdjacent;
                breadthFirstSearch(grid, row, column);
            }
            islands.add(set.size());
        }
        return islands;
    }

    public void breadthFirstSearch(int[][] grid, int row, int column) {
        int m = grid.length, n = grid[0].length;
        int curNumber = grid[row][column];
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{row, column});
        while (!queue.isEmpty()) {
            int[] square = queue.poll();
            int curRow = square[0], curColumn = square[1];
            for (int[] direction : directions) {
                int newRow = curRow + direction[0], newColumn = curColumn + direction[1];
                if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n) {
                    int prevNumber = grid[newRow][newColumn];
                    if (prevNumber > curNumber) {
                        grid[newRow][newColumn] = curNumber;
                        set.remove(prevNumber);
                        queue.offer(new int[]{newRow, newColumn});
                    }
                }
            }
        }
    }
}

All Problems

All Solutions