LC 200 - Number of Islands

Question

Given an m x n 2D binary grid grid which represents a 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.

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Links

Question here and solution here

Solution

concept

Use DFS to search through each cells is one of the easiest way.

Both DFS and BFS aim to search from the current cell and mark all reachable cells in visited set. When the next cell is a land but not in the visited set, then we know this is the start of a new island

code

class Solution:
	"""
	DFS solution
	"""
    def numIslands(self, grid: List[List[str]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        islands = 0
        visited = set()

        def dfs(r, c):
            if (r < 0 or r >= ROW or
                c < 0 or c >= COL or
                (r, c) in visited or 
                grid[r][c] == "0"):
                return

            directions = [[0,1], [1,0], [0, -1], [-1, 0]]
            visited.add((r, c))
            
            for dr, dc in directions:
                dfs(r + dr, c + dc)

        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == "1" and (r, c) not in visited:
                    islands += 1 # only increase when it is an island that is not seen before
                    dfs(r, c)

        return islands
        
class Solution:
	"""
	BFS
	"""
    def numIslands(self, grid: List[List[str]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        visited = set()
        islands = 0
        directions = [[0,1], [0,-1], [-1,0], [1,0]]

        def bfs(r, c):
            q = deque()
            visited.add((r,c))
            q.append((r, c))

            while q:
                row, col = q.popleft()
                for dr, dc in directions:
                    n_r, n_c = row + dr, col + dc
                    if (0 <= n_r < ROW and
                        0 <= n_c < COL and
                        grid[n_r][n_c] == "1" and
                        (n_r, n_c) not in visited):

                        visited.add((n_r, n_c))
                        q.append((n_r, n_c))

        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == "1" and (r,c) not in visited:
                    islands += 1
                    bfs(r,c)

        return islands

Complexity

time: $O(mn)$
space: $O(mn)$