200. Number of Islands

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

Python

DFS with Hashmap

• Time: O(M*N)
• Space: O(K) # K present the block with

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        offsets = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited = set()


        def dfs(row: int, col: int, island: set):
            if grid[row][col] == "0":
                return set()

            island.add((row, col))

            for rx, cx in offsets:
                if row+rx < 0 or row+rx >= m or col+cx < 0 or col+cx >= n:
                    continue
                if (row+rx, col+cx) in island:
                    continue
                island |= dfs(row+rx, col+cx, island)

            return island

        ans = 0
        for row in range(m):
            for col in range(n):
                if grid[row][col] == '0' or (row, col) in visited:
                    continue
                ans += 1
                visited |= dfs(row, col, set())

        return ans