island count

Go Back home

My solution to the island count problem. This uses the sinking technique of setting the entries to 0 to prevent future visits.

The code could look cleaner by putting the checks in the base case, however putting the checks before the function calls results in less calls, and also makes drawing the recursion tree far easier.

 1 # space O(N*M)
 2 # time O(N*M)
 3 
 4 def get_number_of_islands(A):
 5   
 6   def explore_island(i, j):
 7     if A[i][j] == 0:
 8       return
 9     A[i][j] = 0
10 
11     if i > 0:
12       explore_island(i-1, j)
13     if i < len(A)-1:
14       explore_island(i+1, j)
15     if j > 0:
16       explore_island(i, j-1)
17     if j < len(A[0])-1:
18       explore_island(i, j+1)
19 
20   count = 0
21     
22   for i in range(len(A)):
23     for j in range(len(A[0])):
24       if A[i][j] == 1:
25         explore_island(i, j)
26         count += 1
27 
28   return count