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:

1 M = [
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.

1 for 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.

1 def 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 
5 print(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.

1 def 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.

1 num_islands = 0
2 for i in range(len(A)):
3     for j in range(len(A[i])):
4       num_islands += dfs(i, j)
5 print(num_islands) # 3

Bringing it all together

 1 M = [
 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 
 8 def 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 
28 print(number_of_islands(M))
29 
30 print(M)

The equivalent code written more pythonically:

 1 M = [
 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 
 8 def 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 
23 print(number_of_islands(M))
24 
25 print(M)

We can save a bit more space by moving the neighbour logic inside the DFS:

 1 M = [
 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 
 8 def 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 
19 print(number_of_islands(M))

Time and Space Complexity

Attempt it on leetcode.