The problem
A map is an m × n grid of "1" (land) and "0" (water). An island is a group of land cells joined horizontally or vertically, surrounded by water; everything beyond the grid’s edge is water.
Return the number of islands.
Examples
- Input
grid = [ ["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"] ]
- Output
1
- Input
grid = [ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"] ]
- Output
3
Constraints
- 1 ≤ m, n ≤ 300
- Each cell is "0" or "1".
The idea
Scan the grid. The first land cell of each island that the scan meets is where that island is counted — so count it, then make sure none of the island’s other cells can be counted again.
Do that by sinking the island: a depth-first search (here with an explicit stack of cells to visit) spreads from the cell to every land neighbour, turning each into water. When the scan moves on, the whole island is gone, and the next land it meets must be a new island.
- Time
- O(m · n) — each cell sunk at most once
- Space
- O(m · n) — the stack, when the whole map is land
Solution · every language run against every case
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 # new land: sink the whole island so it is counted once grid[r][c] = "0" stack = [(r, c)] while stack: i, j = stack.pop() for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)): if 0 <= x < rows and 0 <= y < cols and grid[x][y] == "1": grid[x][y] = "0" stack.append((x, y)) return islands