Big O Practice: Number Of Islands

def num_islands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or c < 0 or r >= m or c >= n:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

Variables

• m - number of rows in the grid
• n - number of columns in the grid

Explanation

Each cell is visited at most once across all DFS calls - total time **O(m · n)**. The recursion stack can grow to the size of the largest island, which in the worst case is the whole grid - **O(m · n)** auxiliary space.

More Big O practice problems · Today's daily problem