[LC] 200. Number of Islands

Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Approach

Simple breath first search (BFS). Nothing special. Just keep looking for non visited grid and do the BFS and check the visited.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid) == 0:
            return 0
        
        n,m = len(grid), len(grid[0])
        visited = [[False]*m for _ in range(n)]
        q = collections.deque()
        
        k = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1" and not visited[i][j]:
                    q.append((i,j))
                    while q:
                        x,y = q.popleft()
                        if visited[x][y]:
                            continue
                        
                        visited[x][y] = True
                        for x1,y1 in [(0,1), (0,-1), (1,0), (-1,0)]:
                            new_x, new_y = x+x1, y+y1
                            if 0 <= new_x < n and 0 <= new_y < m and grid[new_x][new_y] == "1" and not visited[new_x][new_y]:
                                q.append((new_x, new_y))
                    k += 1
             
        return k
            

Time and Space Complexity: O(N*M)

Submission

Runtime: 140 ms, faster than 68.50% of Python3 online submissions for Number of Islands.Memory Usage: 15.4 MB, less than 72.58% of Python3 online submissions for Number of Islands.