number of islands
Given an m x n 2d grid 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:
Input:
1M = [
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]
Output: 1
Solution
Counting the islands is done in two parts, the first is a linear scan of the matrix.
1for i in range(len(A)):
2 for j in range(len(A[i])):
3 if A[i][j] == 1:
4 """
5 Do something.
6 """
The second part is to recursively "explore" the neighbouring cells. The trick when exploring neighbours is to not fall off the edges of the Matrix.
1def neighbours(i, j):
2 z = zip((i+1, i-1, i, i), (j, j, j+1, j-1))
3 return [(i, j) for i, j in z if 0 <= i < len(M) and 0 <= j < len(M[i])]
4
5print(neighbours(0,0)) # [(1, 0), (0, 1)]
Now that we have the indices of our valid neighbours, we can explore them recursively, i.e perform a DFS.
1def dfs(i, j):
2 if M[i][j] == '1':
3 M[i][j] = '0'
4 for n in neighbours(i, j):
5 dfs(i, j)
6 return 1
7 return 0
We set the cell to "0" as we explore it; this can be referred to as 'sinking' the cell, or can also be thought of as graph colouring. The final step is to return the sum of islands found within our linear scan.
1num_islands = 0
2for i in range(len(A)):
3 for j in range(len(A[i])):
4 num_islands += dfs(i, j)
5print(num_islands) # 3
Bringing it all together
1M = [
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]
7
8def number_of_islands(M):
9 def neighbours(i, j):
10 z = zip((i+1, i-1, i, i), (j, j, j+1, j-1))
11 return [(i, j) for i, j in z if 0 <= i < len(M) and 0 <= j < len(M[i])]
12
13 def dfs(i, j):
14 if M[i][j] == '1':
15 M[i][j] = '0'
16 for ni, nj in neighbours(i, j):
17 dfs(ni, nj)
18 return 1
19 return 0
20
21 num_islands = 0
22 for i in range(len(M)):
23 for j in range(len(M[i])):
24 num_islands += dfs(i, j)
25
26 return num_islands
27
28print(number_of_islands(M))
29
30print(M)
The equivalent code written more pythonically:
1M = [
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]
7
8def number_of_islands(M):
9 def neighbours(i, j):
10 z = zip((i+1, i-1, i, i), (j, j, j+1, j-1))
11 return [(i, j) for i, j in z if 0 <= i < len(M) and 0 <= j < len(M[i])]
12
13 def dfs(i, j):
14 if M[i][j] == '1':
15 M[i][j] = '0'
16 for ni, nj in neighbours(i, j):
17 dfs(ni, nj)
18 return 1
19 return 0
20
21 return sum(dfs(i, j) for i in range(len(M)) for j in range(len(M[0])))
22
23print(number_of_islands(M))
24
25print(M)
We can save a bit more space by moving the neighbour logic inside the DFS:
1M = [
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]
7
8def number_of_islands(M):
9 def dfs(i, j):
10 if M[i][j] == '1' and 0 <= i < len(M) and 0 <= j < len(M[i]):
11 M[i][j] = '0'
12 for ni, nj in zip((i+1, i-1, i, i), (j, j, j+1, j-1)):
13 dfs(ni, nj)
14 return 1
15 return 0
16
17 return sum(dfs(i, j) for i in range(len(M)) for j in range(len(M[0])))
18
19print(number_of_islands(M))
Time and Space Complexity
Attempt it on leetcode.