Number of Islands
Given a 2-D Array, count the number of islands in it, where land is connected in the NSEW direction. Tags: Recursion, Search, Union-Find
Try It!
Discussion
Video
Solution
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs_marking(grid, i, j);
count += 1
return count
def dfs_marking(self, grid, i, j):
if i < 0 or i >= len(grid):
return
if j < 0 or j >= len(grid[0]):
return
if grid[i][j] != '1':
return
grid[i][j] = '0'
self.dfs_marking(grid, i + 1, j)
self.dfs_marking(grid, i - 1, j)
self.dfs_marking(grid, i, j + 1)
self.dfs_marking(grid, i, j - 1)