Number of Islands

The problem description can be found in LeetCode.

Approach

This is a classic and it can be solved with both DFS and BFS.

I personally prefer the recursive DFS approach, which is the one that uses less code. Here, we assume that the input can be changed, so we do not need to keep a visited Set to track the already seen coordinates. However, this is something we need to clarify with the interviewer.

Solution

from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # not ideal, but just to avoid to have too many function parameters
        self.grid = grid
        self.rows, self.cols = len(grid), len(grid[0])

        ans = 0

        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] == "1":
                    self.dfs(row, col)
                    ans += 1

        return ans

    def dfs(self, row: int, col: int) -> None:
        if (
            not (0 <= row < self.rows and 0 <= col < self.cols)
            or self.grid[row][col] == "0"
        ):
            return

        self.grid[row][col] = "0"
        self.dfs(row - 1, col)  # up
        self.dfs(row + 1, col)  # down
        self.dfs(row, col - 1)  # left
        self.dfs(row, col + 1)  # right

Complexity

• Time: $O(mn)$
• Space: $O(mn)$

Where $m$ and $n$ are the number of rows and columns of the input grid, respectively.