Why do we mutate the grid cells to '0' during DFS?

Marking visited land cells as '0' (water) sinks the land so that subsequent outer loop iterations and recursive branches never revisit or double-count the same island. This avoids having to allocate an extra O(m*n) boolean visited array.

Can we solve Number of Islands using BFS instead of DFS?

Yes, you can use a queue to perform Breadth-First Search (BFS). When you find a '1', enqueue its coordinates and sink connected neighbors level by level. BFS avoids call stack recursion depth issues on very large grids.

MediumGraphs & Matrix WalksPattern: Depth-First Search (DFS)Pattern: Breadth-First Search (BFS)Pattern: Connected ComponentsPattern: Matrix Flood Fill

Number of Islands

Count the number of distinct islands in a 2D binary grid. The definitive problem for learning connected components and matrix flood-fill traversals.

Problem Statement

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Examples & Constraints

Example 1

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

Output: 1

Explanation: All adjacent 1s form a single connected landmass.

Example 2

Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]

Output: 3

Explanation: There are three separate islands disconnected from each other by water.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

DFS Flood Fill (In-Place Sink)

Optimal Approach

Time:O(m * n)

Space:O(m * n)

Scan every cell in the grid. Upon finding an unvisited land cell ('1'), increment the island count and recursively sink all horizontally and vertically connected land cells to '0'.

Time ComplexityO(m * n)

Every cell in the M x N grid is visited at most a constant number of times (once by the outer nested loop, and once by the DFS recursive sink).

Space ComplexityO(m * n)

In the worst case where the entire grid is land (all '1's), the recursion stack reaches depth M x N.

Underlying algorithmic logic

The Connected Component Mental Model

In graph theory, a 2D grid of land and water is an undirected graph where:

Each land cell '1' is a vertex.
Adjacent horizontal and vertical land cells share an edge.
An "island" is a connected component.

The Sinking Technique:

To avoid allocating an m x n auxiliary visited boolean matrix, we can "sink" visited land directly by mutating grid[r][c] = '0':

Iterate over every row r from 0 to m - 1 and column c from 0 to n - 1.
When we encounter grid[r][c] == '1':

We have discovered a brand new unvisited island!
Increment our total islandCount++.
Trigger a DFS flood-fill starting at (r, c) to sink this entire island so we never double-count it.

In the DFS function:

Check boundary guards: if r < 0, r >= m, c < 0, c >= n, or grid[r][c] == '0', return immediately.
Sink the current cell: grid[r][c] = '0'.
Recursively call DFS in all 4 cardinal directions:
Up: (r - 1, c)
Down: (r + 1, c)
Left: (r, c - 1)
Right: (r, c + 1)

Return islandCount.

Step-by-step execution walkthrough

First Land Cell (0, 0)

Inspect (0, 0) = '1'. Island count = 1. Trigger DFS flood fill to sink connected landmass.

islands = 1, DFS expanding from (0, 0)

Sink Island 1

DFS visits and marks (0,0), (0,1), (1,0), (1,1) as '0'. Entire top-left landmass sunk.

Top-left 2x2 cluster sunk to '0'

Encounter (2, 2)

Scanner reaches (2, 2) = '1'. Island count = 2. Sunk immediately.

islands = 2

Encounter (3, 3)

Scanner reaches (3, 3) = '1'. Island count = 3. Sinks (3, 3) and (3, 4).

Final count: 3 islands

Advantages

•Zero auxiliary space overhead for a visited matrix (mutates grid in-place)
•Straightforward 4-directional flood fill logic

Trade-offs

•Mutates original grid data (can restore if requested in interview)
•Deep recursion risk on very large grids without iterative BFS

Code Implementations

Ready-to-use

Copy & paste production-ready solutions for DFS Flood Fill (In-Place Sink) in your language of choice

File: solution.py

Python

def num_islands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    islands = 0
    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"  # sink land
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                dfs(r, c)
    return islands
if __name__ == "__main__":
    grid = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"]
    ]
    print("Number of islands:", num_islands(grid))

Interactive visualizer available

Understand BFS & DFS Visually

Traverse complex graph networks using level-order queues and depth-first stacks. Test live edge cases and watch memory state transitions step-by-step.

Launch BFS & DFS Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems

EasyTrees & BST

Visualizer

Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree along the longest path from root to leaf. The quintessential problem for learning bottom-up divide-and-conquer tree recursion.

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))

Learn logic

MediumGraphs & Matrix Walks

Visualizer

Rotting Oranges

Determine the minimum minutes needed until all fresh oranges rot. The premier problem for learning Multi-Source Breadth-First Search (BFS) in grid matrices.

1 approach(O(m * n))

Learn logic