You are given an m x n grid where "1" is land and "0" is water. An island is a group of land cells connected horizontally or vertically (not diagonally), and the grid is surrounded by water on all sides. Return the number of islands.
- 1 <= m, n <= 300
- grid[i][j] is "0" or "1"
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Think of the grid as a graph: every land cell is a node, and it has edges to land cells above, below, left and right. The number of islands is the number of connected components. Scan the grid; when we hit a land cell, it starts a new island, so we count it and immediately "sink" the whole island with a DFS or BFS that turns its cells into water. Later cells of that island are then skipped. Every cell is visited a constant number of times.
Algorithm
- Loop over every cell
(r, c). - If it is
"1", increase the island count. - Push it on a stack and mark it
"0". - While the stack is not empty, pop a cell and push each of its 4 neighbours that is
"1", marking them"0"as you push. - Return the count after the scan.
O(m * n)Space: O(m * n) in the worst case for the stackclass Solution: def numIslands(self, grid: List[List[str]]) -> int: m, n = len(grid), len(grid[0]) count = 0 for r in range(m): for c in range(n): if grid[r][c] != "1": continue count += 1 # new island found stack = [(r, c)] grid[r][c] = "0" while stack: x, y = stack.pop() for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)): if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1": grid[nx][ny] = "0" # sink it when pushed stack.append((nx, ny)) return count