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)