Problem statement

https://leetcode.com/problems/number-of-islands/

Solution

Classical graph-traversal algorithm. I prefer to use dfs, we need to start it from all points, and to change already visited cells to some new symbol, for example #.

Complexity

It is O(mn) for time and space

Code

class Solution:
    def numIslands(self, grid):
        m, n, cnt = len(grid), len(grid[0]), 0
        
        def dfs(i, j):
            if not 0 <= i < m or not 0 <= j < n or grid[i][j] != '1':
                return
            grid[i][j] = '#'
            for x, y in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
                dfs(x, y)
        
        for i, j in product(range(m), range(n)):
            if grid[i][j] == '1':
                dfs(i, j)
                cnt += 1
                
        return cnt