{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Number of Islands – Solution & Complexity

Interview solutions
/
Number of Islands

Watch: Number of Islands with flood fill

Scan the grid. Each time you hit unvisited land, you've found a new island: count it, then flood-fill (DFS or BFS) every connected land cell so it isn't counted again. Every cell is visited once, so it's O(rows × cols).

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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
Learn the Graph Traversal pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Number of Islands online (run code in the browser)01 Matrix solution (medium)Course Schedule solution (medium)Rotting Oranges solution (medium)Longest Increasing Path in a Matrix solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?