Given a 2-D array of 0s and 1s, find islands in it. An Island is 1s together
class Solution(object):
def count_islands(self,arr):
island_count = 0
for i in range(len(arr)):
for j in range(len(arr[i])):
if arr[i][j]:
self._dfs_util(arr,i,j)
island_count+=1
return island_count
def _dfs_util(self,arr,i,j):
if i < len(arr) and i>=0 and j>=0 and j<len(arr[i]) and arr[i][j]==1:
arr[i][j] = 0
self._dfs_util(arr,i-1,j)
self._dfs_util(arr,i+1,j)
self._dfs_util(arr,i,j-1)
self._dfs_util(arr,i,j+1)
Time Complexity is O(m*n) if shape of arr is m,n