# Question

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

# 305. Number of Islands II

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 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 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 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 into a land.

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


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

Union Find.

# Code

Java

## 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, column = position;
if (grid[row][column] != 0) {
continue;
}
for (int[] direction : directions) {
int newRow = row + direction, newColumn = column + direction;
if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n && grid[newRow][newColumn] != 0)
}
islandsCount++;
grid[row][column] = islandsCount;
} else {
}
}
return islands;
}

public void breadthFirstSearch(int[][] grid, int row, int column) {
int m = grid.length, n = grid.length;
int curNumber = grid[row][column];
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue.offer(new int[]{row, column});
while (!queue.isEmpty()) {
int[] square = queue.poll();
int curRow = square, curColumn = square;
for (int[] direction : directions) {
int newRow = curRow + direction, newColumn = curColumn + direction;
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});
}
}
}
}
}
}