Count islands on a torus grid
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates skills in graph and grid algorithms, topology-aware adjacency (torus wrap-around), and maintaining dynamic connectivity under incremental updates.
Part 1: Count Islands on a Torus Grid Using Graph Search
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
Input: ([],)
Expected Output: 0
Explanation: An empty grid contains no land, so the answer is 0.
Input: ([[1]],)
Expected Output: 1
Explanation: A single land cell forms exactly one island.
Input: ([[1, 0], [0, 1]],)
Expected Output: 2
Explanation: The two land cells are diagonal only, so they are not connected.
Input: ([[1, 0, 1]],)
Expected Output: 1
Explanation: In a single-row torus, the first and last columns are adjacent, so the two land cells connect through wrap-around.
Solution
def solution(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
islands = 0
for r in range(m):
for c in range(n):
if grid[r][c] != 1 or visited[r][c]:
continue
islands += 1
stack = [(r, c)]
visited[r][c] = True
while stack:
x, y = stack.pop()
neighbors = [
((x - 1) % m, y),
((x + 1) % m, y),
(x, (y - 1) % n),
(x, (y + 1) % n),
]
for nx, ny in neighbors:
if grid[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
stack.append((nx, ny))
return islandsTime complexity: O(m * n). Space complexity: O(m * n).
Hints
- Use modulo arithmetic when generating the up, down, left, and right neighbors.
- 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
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
Input: ([],)
Expected Output: 0
Explanation: An empty grid has no islands.
Input: ([[1]],)
Expected Output: 1
Explanation: A single land cell is one connected component.
Input: ([[1, 0, 1], [0, 0, 0], [1, 0, 1]],)
Expected Output: 1
Explanation: All four corner land cells connect through torus wrap-around along rows and columns.
Input: ([[1, 0], [0, 1]],)
Expected Output: 2
Explanation: The two land cells do not share a side, so they remain separate islands.
Input: ([[1, 1], [1, 1]],)
Expected Output: 1
Explanation: All cells are land, so the entire grid is one island.
Solution
def solution(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
parent = {}
rank = {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra = find(a)
rb = find(b)
if ra == rb:
return
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
idx = r * n + c
parent[idx] = idx
rank[idx] = 0
if not parent:
return 0
for r in range(m):
for c in range(n):
if grid[r][c] != 1:
continue
a = r * n + c
down_r, down_c = (r + 1) % m, c
if (down_r != r or down_c != c) and grid[down_r][down_c] == 1:
union(a, down_r * n + down_c)
right_r, right_c = r, (c + 1) % n
if (right_r != r or right_c != c) and grid[right_r][right_c] == 1:
union(a, right_r * n + right_c)
roots = set()
for idx in parent:
roots.add(find(idx))
return len(roots)Time complexity: O(m * n * alpha(m * n)). Space complexity: O(m * n).
Hints
- Treat each land cell as a node in a graph and union adjacent land cells.
- 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
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
Input: ([[0, 0], [0, 0]], [(0, 0), (1, 1), (0, 1), (0, 0)])
Expected Output: [1, 2, 1, 1]
Explanation: The updates create, separate, merge, and then partially remove land while preserving torus connectivity rules.
Input: ([[1, 0, 1]], [(0, 1), (0, 0), (0, 2)])
Expected Output: [1, 1, 1]
Explanation: In a single-row torus, the ends are adjacent, so wrap-around keeps the remaining land connected.
Input: ([[1]], [(0, 0), (0, 0)])
Expected Output: [0, 1]
Explanation: The only cell flips from land to water and back again.
Input: ([], [])
Expected Output: []
Explanation: With no grid and no updates, there are no reported counts.
Solution
def solution(grid, updates):
board = [row[:] for row in grid]
def count_islands(curr):
if not curr or not curr[0]:
return 0
m, n = len(curr), len(curr[0])
visited = [[False] * n for _ in range(m)]
islands = 0
for r in range(m):
for c in range(n):
if curr[r][c] != 1 or visited[r][c]:
continue
islands += 1
stack = [(r, c)]
visited[r][c] = True
while stack:
x, y = stack.pop()
neighbors = [
((x - 1) % m, y),
((x + 1) % m, y),
(x, (y - 1) % n),
(x, (y + 1) % n),
]
for nx, ny in neighbors:
if curr[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
stack.append((nx, ny))
return islands
if not updates:
return []
if not board or not board[0]:
return []
result = []
for r, c in updates:
board[r][c] = 1 - board[r][c]
result.append(count_islands(board))
return resultTime complexity: O(k * m * n). Space complexity: O(m * n).
Hints
- Each update toggles a single cell, so update the grid first and then count islands on the new state.
- Given the stated limits, a clean and correct approach is to reuse a torus island-counting helper after every flip.