Number of Islands – Solution & Complexity

Q: What is the time and space complexity of Number of Islands?

The optimal Number of Islands solution runs in `O(m*n)` time and `O(m*n)` space. DFS/BFS flood fill from each unvisited land cell, marking the whole island.

Q: What is the most efficient way to solve Number of Islands?

DFS/BFS flood fill from each unvisited land cell, marking the whole island. This gives `O(m*n)` time complexity, and is a classic matrix, graph, dfs, and bfs problem.

Q: How do you solve Number of Islands in Python & JavaScript?

We provide a worked Number of Islands solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Number of Islands an easy or hard interview question?

Number of Islands is generally rated **Medium**. It tests matrix, graph, dfs, and bfs, which are common coding-interview patterns.

1. Understand the Grid

Each 1 cell is land and each 0 cell is water.
Land cells belong to the same island if they touch horizontally or vertically.
Diagonal contact does not connect islands.
We need to count connected groups of land.

2. Naive Counting Is Not Enough

Counting every land cell would overcount large islands.
Once we discover one land cell, we must find all land connected to it.
That whole connected component should add only one to the answer.

3. Use DFS With a Visited Set

Scan every cell in the grid.
When an unvisited land cell is found, it starts a new island.
Run DFS from that cell to mark every connected land cell as visited.
Using a visited set avoids mutating the input grid.

visited = set()

def dfs(row, col):
    if row < 0 or row == rows or col < 0 or col == cols:
        return
    if grid[row][col] != '1' or (row, col) in visited:
        return

    visited.add((row, col))
    dfs(row + 1, col)
    dfs(row - 1, col)
    dfs(row, col + 1)
    dfs(row, col - 1)

4. Count Island Starts

Only increment the island count when the scan finds land that has not been visited.
The DFS then visits the entire island, so future cells from the same island are skipped.

islands = 0
for row in range(rows):
    for col in range(cols):
        if grid[row][col] == '1' and (row, col) not in visited:
            islands += 1
            dfs(row, col)

5. Final Solution and Complexity

Handle an empty grid before reading dimensions.
Each cell is visited at most once.
Time complexity is O(rows × cols).
Space complexity is O(rows × cols) for the visited set and recursion stack in the worst case.

def num_islands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    visited = set()

    def dfs(row, col):
        if row < 0 or row == rows or col < 0 or col == cols:
            return
        if grid[row][col] != '1' or (row, col) in visited:
            return

        visited.add((row, col))
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    islands = 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == '1' and (row, col) not in visited:
                islands += 1
                dfs(row, col)

    return islands

Number of Islands – Solution & Complexity

1. Understand the Grid

2. Naive Counting Is Not Enough

3. Use DFS With a Visited Set

4. Count Island Starts

5. Final Solution and Complexity

FAQ

What is the time and space complexity of Number of Islands?

What is the most efficient way to solve Number of Islands?

How do you solve Number of Islands in Python & JavaScript?

Is Number of Islands an easy or hard interview question?