Examples / Grid BFS (islands)▶Run in PyTrace
Number of Islands: Grid BFS Visualization
Many interview problems hide a graph inside a 2D grid: every cell is a node connected to its four neighbors. To count islands you scan the grid, and every time you find unvisited land you start a BFS that sinks the whole island by turning its cells into water.
PyTrace renders the grid as a matrix with r/c and i/j as row and column pointers, so you can watch the flood fill spread from cell to cell.
ComplexityO(rows × cols) time; O(min(rows, cols)) queue space for BFS.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1":
continue
islands += 1
grid[r][c] = "0"
queue = deque([(r, c)])
while queue:
i, j = queue.popleft()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == "1":
grid[ni][nj] = "0"
queue.append((ni, nj))
return islandsInputs
grid[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
expected3
What to watch
- The
gridmatrix, with cells flipping from"1"to"0" - The
queueof coordinates waiting to be explored islandsincreasing only when the scan finds new land