intermediate8 min read·Updated October 1, 2026

Number of Islands Explained: Tracing DFS & BFS on a 4×5 Grid

Master the Number of Islands algorithm with a step-by-step walkthrough of a 4×5 grid. Learn the flood fill mental model, DFS/BFS, and time complexity.

By Learnisim AI·Published October 1, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • 2D arrays and matrices
  • Basic recursion or queue data structures
  • Graph traversal fundamentals
Number of Islands (DFS / BFS Flood Fill) Counting 4-connected components in a 4×5 grid 4×5 Grid Matrix '1' = Land, '0' = Water 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Graph Representation • Nodes = '1' land cells • Edges = Orthogonal neighbors • Goal = Count Connected Components (Islands) DFS / BFS Flood Fill Steps Scan matrix & sink visited land 1 Island 1 Found at (0,0) Launch DFS: visits (0,1), (1,0), (1,1) Mutates all 4 cells to '0'. Count = 1 2 Island 2 Found at (2,2) Check 4 orthogonal neighbors: all '0' Mutates (2,2) to '0'. Count = 2 3 Island 3 Found at (3,3) Launch DFS: visits (3,4) Mutates both to '0'. Count = 3 Algorithm Output Final traversal result Total Islands Count 3 def numIslands(grid): count = 0 for r in range(rows): for c in range(cols): if grid[r][c] == '1': count += 1 dfs(grid, r, c) return count
Islands in a 4×5 grid with two land blobs overview diagram
Why

Why Count Connected Land Blobs? The Spatial Counting Dilemma

Phase 1: The Grid Counting Problem

Imagine staring at a satellite map of an archipelago represented as a 2D grid of strings, where "1" denotes land and "0" denotes water. Our mission is to count how many distinct islands exist in this matrix. Without a systematic approach, our eyes easily miscount or accidentally bridge separate landmasses that touch diagonally instead of orthogonally.
Consider our locked working example, a grid:
python
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
If you scan this matrix from top-left to bottom-right, you encounter clusters of "1"s separated by barriers of "0"s. But how do we prove mathematically that the top-left block of four "1"s is a single connected entity, while the lone "1" at coordinate is separate, and the pair at the bottom-right forms a third? Without an automated exploration strategy like DFS or BFS flood fill, software cannot reliably distinguish adjacent contiguous regions from distant ones.
python
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
Number of Islands: DFS / BFS Flood Fill (4×5 Grid) Matrix Map (1 = Land, 0 = Water) 1 (0,0) 1 (0,1) 0 0 0 1 (1,0) 1 (1,1) 0 0 0 0 0 1 (2,2) 0 0 0 0 0 1 (3,3) 1 (3,4) Island #1: Top-Left Cluster (4 cells) Island #2: Lone Cell (2,2) Island #3: Bottom-Right Pair (2 cells) DFS / BFS Flood Fill Algorithm 1. Linear Scan for Unvisited '1' Traverse grid. When grid[r][c] == '1' and not visited, increment island counter and trigger flood fill! 2. Recursive Flood Fill (DFS / BFS) Mark current cell as visited ('0' or visited set). Explore 4 orthogonal directions (Up, Down, Left, Right). 3. Sinking Land & Final Result Connected land is fully consumed/sunk per island. Total Count = 3 Distinct Islands Found!
Why Count Connected Land Blobs? The Spatial Counting Dilemma diagram
Model

The Island Grid Model: Turning Pictures Into Connected Graph Components

Phase 2: The Island Grid Model

To count how many distinct land blobs exist in our locked working example, we must stop looking at the grid as a picture and start looking at it as an undirected graph.
Consider our given grid:
python
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
Every cell containing "1" represents a node, and every adjacent "1" directly to the north, south, east, or west represents an edge connecting those nodes. Diagonal neighbors do not count as edges, which is why the lone "1" at grid[2][2] remains entirely isolated from the top-left block.
Our goal becomes finding the number of connected components in this grid graph. When we encounter an unvisited "1", we have discovered a new island. We then use a flood-fill traversal (using either DFS or BFS) to explore and mark every reachable land cell belonging to that exact component before resuming our scan of the grid.
python
def get_neighbors(r, c, rows, cols):
    # Return valid orthogonal (up, down, left, right) coordinate tuples
    pass
The Island Grid Model: Turning Pictures Into Connected Graph Components 4 × 5 Grid Graph (2 Islands) 1 (0,0) 1 (0,1) 0 (0,2) 0 (0,3) 0 (0,4) 1 (1,0) 1 (1,1) 0 (1,2) 0 (1,3) 0 (1,4) 0 (2,0) 0 (2,1) 1 (2,2) 0 (2,3) 0 (2,4) 0 (3,0) 0 (3,1) 0 (3,2) 1 (3,3) 1 (3,4) Nodes = '1' (Land) | Edges = North/South/East/West Diagonals do not connect components! Flood Fill DFS / BFS Flood-Fill Mechanism 1. Scan Grid & Find Unvisited Land ('1') Counter increments! Found new Island component. ans++ (Total Islands found so far) 2. Exhaustive Traversal (Sink the Island) DFS / BFS visits all 4 orthogonal neighbors: Mark '1' → '0' (or visited set) so we never recount Prevents infinite loops & duplicate counting 3. Resume Grid Scan Continue scanning until all cells are processed. Final Result: Exactly 2 Islands
The Island Grid Model: Turning Pictures Into Connected Graph Components diagram
Worked example

Tracing the 4×5 Island Grid: Step-by-Step Flood Fill Execution

Phase 3: Working Through the 4×5 Grid Trace

Let us execute our graph exploration model on the locked 4×5 grid. Our algorithm scans every cell, and whenever it hits an unvisited "1", it triggers a flood fill (DFS or BFS) to sink the entire connected land blob by turning "1" into "0", incrementing our island counter along the way.

Given

Steps

- Row 0, Col 0: We find "1". Increment count = 1. We launch DFS from (0,0). It visits (0,1), (1,0), and (1,1), mutating all four cells to "0".
- Scan continues: Rows 0 and 1 are now entirely "0". We skip over water cells until Row 2, Col 2.
- Row 2, Col 2: We find "1". Increment count = 2. DFS from (2,2) checks orthogonal neighbors: all are "0". Mutate (2,2) to "0" and return.
•Scan continues: Row 3, Col 0 through 2 are water. We reach Row 3, Col 3.

- Row 3, Col 3: We find "1". Increment count = 3. DFS from (3,3) visits (3,4), mutating both to "0".

Result

After scanning the entire 4×5 grid, the final count is exactly 3.
Try this: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Practice

Predicting the DFS Sink: Tracing a Modified 4×5 Island Grid

Phase 4: Practice

Now that you have traced the original grid, let us test your understanding of how orthogonal reachability dictates the final island count. Consider a modified version of our grid where the solitary middle land cell at row 2, column 2 is connected to the top blob.
Given the modified grid:
python
grid = [
    ["1", "1", "1", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
Your task is to mentally execute the flood fill or write out the state changes. Specifically, determine how many total islands will be counted by the outer loop after all recursive DFS calls or queue expansions complete.
python
grid = [
    ["1", "1", "1", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
# Question: How many islands does this modified grid produce, 
# and which cells belong to the second island encountered?
Apply

Beyond Grids: Transferring Flood Fill to Image Regions

Phase 5: Applying Grid Traversal to Other Domains

Now that you have traced how the 4-connected flood fill processes our land-and-water grid, it is time to decouple the core pattern from matrices and numbers. The underlying concept—finding connected components in an undirected graph via local adjacency—appears across computer graphics, PCB routing, social network clusters, and medical imaging. Whenever you need to count discrete entities formed by touching pixels or relational links, the DFS/BFS clearing technique applies directly.
Consider a monochromatic bitmap image represented as a 2D array of pixels, where pixels are either black (background) or white (foreground). Counting distinct white shapes in the image is structurally identical to our island-counting problem. Instead of looking for "1" strings in a grid, you look for foreground pixels and sink the entire connected blob to avoid double-counting.
To test this transfer, consider how you would adapt your algorithm if diagonal connections were suddenly allowed. In our 4×5 grid, diagonal neighbors like grid[0][1] and grid[1][2] were treated as separate components. If the rules change to 8-connected adjacency, your traversal helper function must check eight directional offsets instead of four. The time complexity remains because each pixel is still visited a constant number of times, but the branching factor of the search increases.
python
def count_8_connected_blobs(grid):
    # Changing from 4-connected to 8-connected traversal
    directions = [
        (-1, 0), (1, 0), (0, -1), (0, 1),
        (-1, -1), (-1, 1), (1, -1), (1, 1)
    ]
    # ... same DFS/BFS sink loop ...
python
def count_8_connected_blobs(grid):
    # Adapt the 4-connected DFS approach to support 8 directions.
    pass

FAQ

How many islands are found in the 4×5 working example grid?
The 4×5 grid contains 3 distinct islands: a top-left 2×2 block, a single land cell at (2,2), and a bottom-right 1×2 horizontal strip.
When should I use DFS versus BFS for the Number of Islands problem?
Both DFS and BFS yield an O(M × N) time complexity. DFS uses the call stack for recursion, which is concise but risks stack overflow on massive grids. BFS uses an explicit queue, avoiding stack overflow limits.
What is the time and space complexity of the flood fill approach?
The time complexity is O(M × N) because every cell in the M×N grid is visited at most once. The space complexity is O(M × N) in the worst-case scenario due to recursive call stack frames or the BFS queue.
What are common pitfalls when implementing grid flood fill?
Common pitfalls include forgetting to mark visited cells (leading to infinite loops), failing to check boundary conditions (index out of bounds), and mutating the original grid without permission.

Keep learning