Count islands on a torus grid

You are given an m x n binary grid representing water (0) and land (1) laid out on a torus: the top edge is adjacent to the bottom edge and the left edge is adjacent to the right edge. Two land cells are connected if they share a side (4-directional), considering wrap-around adjacency. Return the number of connected land components (islands). Follow-ups: (1) Provide two distinct approaches (e.g., graph search and disjoint-set). (2) Analyze the time and space complexities. (3) Extend the solution to support a stream of single-cell flips between 0 and 1 and report the island count after each update.

Part 1: Count Islands on a Torus Grid Using Graph Search

You are given a binary grid where 1 represents land and 0 represents water. The grid is wrapped on a torus: the top row is adjacent to the bottom row, and the leftmost column is adjacent to the rightmost column. Two land cells belong to the same island if they are connected 4-directionally, including wrap-around connections. Write a graph-search solution using DFS or BFS that returns the number of islands.

Constraints

• 0 <= m, n <= 200
• Each grid[i][j] is either 0 or 1
• If m > 0, then n > 0
• Connections are 4-directional only; diagonals do not connect

Examples

Example 1

Input: ([],)
Output: 0

Explanation: An empty grid contains no land, so the answer is 0.

Example 2

Input: ([[1]],)
Output: 1

Explanation: A single land cell forms exactly one island.

Hints

1. Use modulo arithmetic when generating the up, down, left, and right neighbors.
2. Scan every cell; each time you find unvisited land, start a DFS/BFS and count one new island.

Part 2: Count Islands on a Torus Grid Using Disjoint-Set

You are given a binary grid where 1 represents land and 0 represents water. The grid is wrapped on a torus: the top row is adjacent to the bottom row, and the leftmost column is adjacent to the rightmost column. Two land cells belong to the same island if they are connected 4-directionally, including wrap-around connections. Solve the problem using a disjoint-set union data structure (union-find).

Constraints

• 0 <= m, n <= 200
• Each grid[i][j] is either 0 or 1
• If m > 0, then n > 0
• Connections are 4-directional only; diagonals do not connect

Examples

Example 1

Input: ([],)
Output: 0

Explanation: An empty grid has no islands.

Example 2

Input: ([[1]],)
Output: 1

Explanation: A single land cell is one connected component.

Hints

1. Treat each land cell as a node in a graph and union adjacent land cells.
2. To avoid redundant work, it is enough to union each land cell with only its right and down neighbors, while still applying wrap-around.

Part 3: Island Counts After a Stream of Torus Grid Flips

You are given an initial binary grid on a torus, where 1 is land and 0 is water. The top row is adjacent to the bottom row, and the leftmost column is adjacent to the rightmost column. You are also given a list of updates. Each update is a pair (r, c) that flips grid[r][c] between 0 and 1. After each flip, report the current number of islands using 4-directional torus adjacency.

Constraints

• 0 <= m, n <= 50
• 0 <= k <= 200, where k is the number of updates
• Each grid[i][j] is either 0 or 1
• If m > 0, then n > 0
• For every update (r, c), 0 <= r < m and 0 <= c < n

Examples

Example 1

Input: ([[0, 0], [0, 0]], [(0, 0), (1, 1), (0, 1), (0, 0)])
Output: [1, 2, 1, 1]

Explanation: The updates create, separate, merge, and then partially remove land while preserving torus connectivity rules.

Example 2

Input: ([[1, 0, 1]], [(0, 1), (0, 0), (0, 2)])
Output: [1, 1, 1]

Explanation: In a single-row torus, the ends are adjacent, so wrap-around keeps the remaining land connected.

Hints

1. Each update toggles a single cell, so update the grid first and then count islands on the new state.
2. Given the stated limits, a clean and correct approach is to reuse a torus island-counting helper after every flip.