0200_Number_of_Islands.py

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        '''BFS
        One can simply change queue to stack to use DFS instead. Complexity is the same.
        '''
        if not grid:
            return 0
        from collections import deque
        queue = deque()
        ans = 0
        width, length = len(grid[0]), len(grid)
        directions = ((0, 1), (1, 0), (0, -1), (-1, 0))
        for i in range(length):
            for j in range(width):
                if grid[i][j] == '1':
                    ans += 1
                    queue.append((i, j))
                    grid[i][j] = '0'
                    while queue:
                        i2, j2 = queue.popleft()
                        for ii, jj in directions:
                            new_i, new_j = i2 + ii, j2 + jj
                            if 0 <= new_i < length and 0 <= new_j < width and grid[new_i][new_j] == '1':
                                queue.append((new_i, new_j))
                                grid[new_i][new_j] = '0'
        return ans
        
        '''
        Runtime: 152 ms, faster than 45.13% of Python3 online submissions for Number of Islands.
        Memory Usage: 14.1 MB, less than 22.22% of Python3 online submissions for Number of Islands.
        '''
        # def check_island_size(i, j):
        #     if not(0 <= i < len(grid) and 0 <= j < len(grid[0])) or grid[i][j] == '0' or cache[i][j] == -2:
        #         return
        #     cache[i][j] = -2
        #     check_island_size(i-1, j)
        #     check_island_size(i+1, j)
        #     check_island_size(i, j-1)
        #     check_island_size(i, j+1)
        
        # # use a cache matrix where -1 means haven't traverse -2 means traversed
        # cache = [[-1] * len(grid[0]) for _ in range(len(grid))]
        # count = 0
        
        # for i in range(len(grid)):
        #     for j in range(len(grid[0])):
        #         if cache[i][j] == -2 or grid[i][j] == '0':
        #             continue
                
        #         count += 1
        #         check_island_size(i, j)
        
        # return count