Number of Islands

01 · Question

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

Example:

Input: grid = [["1","1","0"],["1","0","0"],["0","0","1"]]
Output: 2

02 · Solution

Reference solution

1def numIslands(grid: List[List[str]]) -> int:
2    rows, cols = len(grid), len(grid[0])
3    islands = 0
4    
5    def dfs(r: int, c: int) -> None:
6        if r < 0 or r >= rows or c < 0 or c >= cols:
7            return
8        if grid[r][c] != '1':
9            return
10        grid[r][c] = '0'
11        dfs(r + 1, c)
12        dfs(r - 1, c)
13        dfs(r, c + 1)
14        dfs(r, c - 1)
15    
16    for r in range(rows):
17        for c in range(cols):
18            if grid[r][c] == '1':
19                islands += 1
20                dfs(r, c)
21    
22    return islands

Flood Fill