200. Number of Islands
## description
## 200. Number of Islands
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.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
1Input: grid = [
2 ["1","1","1","1","0"],
3 ["1","1","0","1","0"],
4 ["1","1","0","0","0"],
5 ["0","0","0","0","0"]
6]
7Output: 1Example 2:
1Input: grid = [
2 ["1","1","0","0","0"],
3 ["1","1","0","0","0"],
4 ["0","0","1","0","0"],
5 ["0","0","0","1","1"]
6]
7Output: 3- –m == grid.length
- –n == grid[i].length
- –1 <= m, n <= 300
- –grid[i][j] is '0' or '1'.
Constraints:
## notes
### Intuition
Whenever we see an island, we should mark the whole island as visited.
### Implementation
We can solve this by iterating over the entire grid and whenever we see an island (1), we mark the whole island as visited with DFS and flipping the node to 0.
We start by iterating over the whole grid:
- –On each iteration, if the node is 1, we call a recursive function consume(i, j) that will use DFS to mark the whole island as visited.
- –We also increment our global count here.
For the consume(i, j) function:
- –If the node at i,j is not 1, we return early
- –Otherwise, we mark that node as visited by flipping it to 0
- –Next, we iterate over all 4 (at most 4, can be less if at edge) neighbours of i,j and call the function recursively
This means that after the consume function is called on a 1 in the main iteration, the whole island will be marked as 0 and we can continue iterating.
### Edge-cases
The neighbours should be checked to ensure they are in bounds correctly.
- –Time: O(m * n), we iterate over the entire grid once and recursively mark each island as visited. In the worst-case, the whole grid is an island so we will only go over all nodes once in the recursive function.
- –Space: O(m * n), for the recursive call stack
### Complexity
## solution
1from typing import List, Tuple
2
3class Solution:
4 def numIslands(self, grid: List[List[str]]) -> int:
5 n = len(grid)
6 m = len(grid[0])
7
8 def neighbs(i: int, j: int) -> List[Tuple[int, int]]:
9 dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
10 res = []
11 for di, dj in dirs:
12 ni = i + di
13 nj = j + dj
14 if ni < 0 or ni >= len(grid) or nj < 0 or nj >= m:
15 continue
16 res.append((ni, nj))
17 return res
18
19
20 def consume(i: int, j: int):
21 if grid[i][j] != "1":
22 return
23 grid[i][j] = "0"
24 for ni, nj in neighbs(i, j):
25 consume(ni, nj)
26
27 count = 0
28 for i in range(n):
29 for j in range(m):
30 if grid[i][j] == "1":
31 count += 1
32 consume(i, j)
33
34 return count
35
36
37
38if __name__ == "__main__":
39 # Include one-off tests here or debugging logic that can be run by running this file
40 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
41 solution = Solution()
42