Number of Islands · DSA Prep

Scan the grid. Every time you find land that you haven’t visited yet, it must be the start of a new island — so flood-fill outward from it (up/down/left/right) marking every connected piece of land as visited, then keep scanning. The number of times you start a fresh flood-fill is the number of islands.

DFS with a Visited Set

Time O(m·n)Space O(m·n)

Depth-first search from every unvisited land cell, tracking visited cells in a separate set so we never flood the same island twice.

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def dfs(r, c):
            if (
                r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == '0' or (r, c) in visited
            ):
                return
            visited.add((r, c))
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc)

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

Correct and already O(m·n) time since every cell is visited a constant number of times — but it pays for a separate visited set on top of the input grid.

DFS by Sinking Islands (In-Place)

OptimalTime O(m·n)Space O(m·n)

Instead of a separate visited set, mutate the grid itself: once a land cell is visited, flip it to '0' (“sink” it). It can never be mistaken for unvisited land again, and we avoid a whole extra data structure.

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
                return
            grid[r][c] = '0'  # sink this land so we never revisit it
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc)

        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(r, c)
                    islands += 1
        return islands

Tracing a small grid [[1,1,0],[0,1,0],[0,0,1]] (row-major scan, flood-filling each new island found):

islands found = 0

1 / 6

landwatervisitedcurrent

Scan hits land at (0,0). Start a DFS flood fill — this will become island #1.

Why it’s correct: flood-filling from a cell visits exactly the cells reachable from it through land — i.e. exactly one island — and sinking prevents ever counting the same island twice or re-entering it. Complexity: every cell is visited (and sunk) at most once, and each visit does O(1) work checking 4 neighbors → O(m·n) time. Space is dominated by the recursion stack, which in the worst case (one giant winding island) can hold all m·n cells → O(m·n) space — but unlike the first approach, there’s no second full-grid data structure alongside it.