Largest Connected Island¶
Find the largest connected component in a binary grid, the same flood-fill logic that OpenCV uses for connected-component labeling in image segmentation.
Problem¶
Given a 2D matrix of 1s (land) and 0s (water), find the size of the largest island. An island is a group of 1s connected horizontally or vertically (not diagonally).
example_world = [
[0, 1, 1, 1, 0, 1, 1, 0],
[1, 1, 0, 1, 0, 0, 1, 1],
[0, 1, 1, 1, 0, 1, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 1, 1, 0],
]
# Answer: 10
Approach¶
Use depth-first search (DFS) from every unvisited land cell. Each DFS explores all reachable land cells, marking them visited as it goes. The recursion returns the count of cells in that component. Track the global max across all DFS calls.
Marking cells in-place (setting visited cells to -1) avoids allocating a separate visited set.
Implementation¶
def get_largest_island_size(world):
def dfs(row, col):
if (row < 0 or row >= len(world) or
col < 0 or col >= len(world[0]) or
world[row][col] != 1):
return 0
world[row][col] = -1 # mark visited
return (1 + dfs(row + 1, col) + dfs(row - 1, col)
+ dfs(row, col + 1) + dfs(row, col - 1))
max_size = 0
for i in range(len(world)):
for j in range(len(world[0])):
if world[i][j] == 1:
max_size = max(max_size, dfs(i, j))
return max_size
example_world = [
[0, 1, 1, 1, 0, 1, 1, 0],
[1, 1, 0, 1, 0, 0, 1, 1],
[0, 1, 1, 1, 0, 1, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 1, 1, 0],
]
assert get_largest_island_size(example_world) == 10
Complexity¶
- Time: O(R * C), each cell visited at most once
- Space: O(R * C), recursion stack in the worst case
Takeaway¶
BFS works equally well here and avoids deep recursion on large grids, worth considering if the input is big enough to blow the call stack.