LC200. Number of Islands

Approach 1: Depth-First Search

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        seen = set()
        m, n = len(grid), len(grid[0])
 
        def dfs(r, c):
            seen.add((r, c))
 
            for (i, j) in [(r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c)]:
                if 0 <= i < m and 0 <= j < n and grid[i][j] == '1' and (i, j) not in seen:
                    dfs(i, j)
                    
        count = 0 
        
        for r in range(m):
            for c in range(n):
                if (r, c) not in seen and grid[r][c] == '1':
                    dfs(r, c)
                    count += 1
        
        return count

Complexity

Time: $O(n)$
Space: $O(n)$