# LeetCode 305: Number of Islands II ## Problem Restatement We are given an empty `m x n` grid filled with water. Each operation turns one cell into land. After every operation, return the current number of islands. An island is a group of connected land cells connected horizontally or vertically. The official problem defines: | Value | Meaning | |---|---| | `0` | Water | | `1` | Land | The grid starts entirely with water. For each position in `positions`, we add land at that location and report the island count after the addition. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0300-0399/0305.Number%20of%20Islands%20II/README_EN.md?utm_source=chatgpt.com)) ## Input and Output | Item | Meaning | |---|---| | Input | Integers `m`, `n`, and a list `positions` | | Operation | Convert one water cell into land | | Output | Island count after each operation | | Connectivity | Horizontal and vertical only | Function shape: ```python def numIslands2( m: int, n: int, positions: list[list[int]], ) -> list[int]: ... ``` ## Examples Example: ```python m = 3 n = 3 positions = [ [0, 0], [0, 1], [1, 2], [2, 1], ] ``` Initially: ```text 0 0 0 0 0 0 0 0 0 ``` Add `(0, 0)`: ```text 1 0 0 0 0 0 0 0 0 ``` There is one island. Output so far: ```python [1] ``` Add `(0, 1)`: ```text 1 1 0 0 0 0 0 0 0 ``` The new land touches the existing island, so the island count stays `1`. Output: ```python [1, 1] ``` Add `(1, 2)`: ```text 1 1 0 0 0 1 0 0 0 ``` This creates a second separate island. Output: ```python [1, 1, 2] ``` Add `(2, 1)`: ```text 1 1 0 0 0 1 0 1 0 ``` Still disconnected. Final output: ```python [1, 1, 2, 3] ``` ## First Thought: DFS After Every Operation One idea is: 1. Add the new land. 2. Scan the entire grid. 3. Run DFS or BFS to count islands. This works. But after every operation, we may scan the whole grid again. If there are many operations, this becomes very slow. Suppose: | Symbol | Meaning | |---|---| | `k` | Number of operations | | `m * n` | Grid size | The complexity becomes roughly: ```python O(k * m * n) ``` We need something incremental. ## Key Insight When adding one land cell, only nearby cells matter. The new land can only connect to its four neighbors: | Direction | Offset | |---|---| | Up | `(-1, 0)` | | Down | `(1, 0)` | | Left | `(0, -1)` | | Right | `(0, 1)` | This is a dynamic connectivity problem. Union-Find, also called Disjoint Set Union (DSU), is designed for this. Each island becomes one connected component. When two neighboring lands touch, we merge their components. ## Union-Find Structure We maintain: | Structure | Meaning | |---|---| | `parent[i]` | Parent of node `i` | | `rank[i]` | Approximate tree height | | `count` | Current number of islands | Each cell maps to one integer id: $$ id=r\cdot n+c $$ For example, in a `3 x 3` grid: | Cell | ID | |---|---:| | `(0, 0)` | `0` | | `(0, 1)` | `1` | | `(1, 0)` | `3` | | `(2, 2)` | `8` | ## Union-Find Operations We need two core operations. ### Find `find(x)` returns the root of the connected component containing `x`. We also use path compression. ```python def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] ``` Path compression makes future operations faster. ### Union `union(a, b)` merges two components. If the roots are already equal, the cells already belong to the same island. Otherwise: 1. Merge the two trees. 2. Decrease island count by one. ```python if root_a != root_b: parent[root_b] = root_a count -= 1 ``` ## Algorithm Initially: 1. All cells are water. 2. Island count is `0`. For each operation `(r, c)`: 1. If the cell is already land, append the current count. 2. Otherwise: - Convert the cell to land. - Increase island count by one. 3. Check all four neighbors. 4. If a neighbor is land: - Union the two cells. 5. Append the island count. ## Correctness Initially, the grid contains no land, so the island count is correctly `0`. When a new land cell is added, it initially forms a new island by itself. Therefore, increasing the count by one is correct. The only way this new land can affect existing islands is through its four neighboring cells. If a neighboring cell is water, no connection exists. If a neighboring cell is land, then the two cells belong to the same island and their connected components should be merged. Union-Find maintains exactly one connected component for each island. When two neighboring land cells belong to different components, merging them correctly reduces the island count by one. If they already belong to the same component, no merge occurs and the count stays unchanged. Since every possible connection caused by the new land is processed, the Union-Find structure always represents the exact island partition of the grid. Therefore, after every operation, the stored island count is correct. ## Complexity | Operation | Complexity | Why | |---|---|---| | Add land | Nearly `O(1)` | At most four unions | | `find` / `union` | Amortized almost constant | Path compression + union by rank | | Total | `O(k α(mn))` | `α` is inverse Ackermann function | `α(n)` grows extremely slowly and is effectively constant in practice. ## Implementation ```python class UnionFind: def __init__(self, size: int): self.parent = list(range(size)) self.rank = [0] * size self.count = 0 def find(self, x: int) -> int: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, a: int, b: int) -> bool: root_a = self.find(a) root_b = self.find(b) if root_a == root_b: return False if self.rank[root_a] < self.rank[root_b]: root_a, root_b = root_b, root_a self.parent[root_b] = root_a if self.rank[root_a] == self.rank[root_b]: self.rank[root_a] += 1 self.count -= 1 return True class Solution: def numIslands2( self, m: int, n: int, positions: list[list[int]], ) -> list[int]: uf = UnionFind(m * n) land = set() ans = [] directions = [ (-1, 0), (1, 0), (0, -1), (0, 1), ] for r, c in positions: if (r, c) in land: ans.append(uf.count) continue land.add((r, c)) uf.count += 1 node_id = r * n + c for dr, dc in directions: nr = r + dr nc = c + dc if not (0 <= nr < m and 0 <= nc < n): continue if (nr, nc) not in land: continue neighbor_id = nr * n + nc uf.union(node_id, neighbor_id) ans.append(uf.count) return ans ``` ## Code Explanation The Union-Find constructor initializes: ```python self.parent = list(range(size)) ``` Each node starts as its own parent. Initially, every node forms its own component. `rank` helps keep trees shallow. ```python self.rank = [0] * size ``` The `find` operation follows parent pointers until reaching the root. ```python if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) ``` This line performs path compression. After compression, future searches become faster. The `union` method first finds both roots. ```python root_a = self.find(a) root_b = self.find(b) ``` If the roots match, both nodes already belong to the same island. ```python if root_a == root_b: return False ``` Otherwise, merge the smaller-rank tree under the larger-rank tree. ```python if self.rank[root_a] < self.rank[root_b]: root_a, root_b = root_b, root_a ``` Then connect: ```python self.parent[root_b] = root_a ``` Since two islands became one, reduce the count. ```python self.count -= 1 ``` Now look at the main solution. We store land cells in: ```python land = set() ``` Water cells are simply absent from the set. For each new position: ```python if (r, c) in land: ``` Duplicate additions do nothing. Otherwise: ```python land.add((r, c)) uf.count += 1 ``` The new land starts as a new island. Convert coordinates to node ids: ```python node_id = r * n + c ``` Then inspect all four neighbors. ```python for dr, dc in directions: ``` If a neighbor exists and is land: ```python uf.union(node_id, neighbor_id) ``` The union operation automatically merges islands if needed. Finally append the island count. ## Testing ```python def run_tests(): s = Solution() assert s.numIslands2( 3, 3, [[0, 0], [0, 1], [1, 2], [2, 1]], ) == [1, 1, 2, 3] assert s.numIslands2( 1, 1, [[0, 0]], ) == [1] assert s.numIslands2( 2, 2, [[0, 0], [1, 1]], ) == [1, 2] assert s.numIslands2( 2, 2, [[0, 0], [0, 1], [1, 1]], ) == [1, 1, 1] assert s.numIslands2( 3, 3, [[0, 0], [0, 0]], ) == [1, 1] assert s.numIslands2( 3, 3, [[0, 0], [1, 0], [2, 0]], ) == [1, 1, 1] print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | Official-style example | Standard island merging | | Single cell | Smallest valid grid | | Separate lands | Multiple disconnected islands | | Connecting neighbors | Merging into one island | | Duplicate additions | Adding same land twice | | Vertical chain | Repeated unions through neighbors |