Understanding Number of Islands | Flood Fill & Graph DFS Explained

How to Solve “Number of Islands” Using Flood Fill and Graph Traversal

When solving grid-based problems, it often feels confusing when explanations suddenly label the problem as a “graph problem” even though no graph is visible. This article explains the Number of Islands problem by connecting it to a much more intuitive idea — the 4-connected flood fill algorithm commonly taught in computer graphics.

Problem Overview

You are given a 2D grid containing "1" (land) and "0" (water). An island is formed when land cells are connected horizontally or vertically. The task is to count how many such islands exist in the grid.

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

Output: 3

Thinking in Terms of Flood Fill

If you have previously implemented flood fill in computer graphics, this problem should feel familiar. In flood fill, we start from a pixel and keep filling neighboring pixels until we hit a boundary or a different color.

In this problem:

• Land ("1") acts as the target color
• Water ("0") acts as the boundary
• Up, down, left, and right represent 4-connected neighbors

Once we encounter a land cell, we “fill” the entire connected region and mark it as visited.

Where the Graph Comes In

Although no graph is explicitly drawn, the grid itself forms an implicit graph. Each cell is a node, and each cell is connected to its adjacent neighbors.

• Each grid cell is a node
• Edges exist between horizontally and vertically adjacent cells
• Only land cells ("1") are considered part of the graph

This is why the problem is often described as a graph traversal problem. We are simply traversing connected components in an implicit graph.

Depth-First Search (DFS) Traversal

The solution works by scanning the grid cell by cell. Whenever an unvisited land cell is found, a depth-first search is started to visit all connected land cells.

1. Traverse the entire grid
2. When land is found, increment the island count
3. Use DFS to visit and mark all connected land cells
4. Continue until all cells are processed

Marking a cell as visited is done by converting land ("1") into water ("0"). This prevents the same island from being counted multiple times.

Core DFS Logic

def dfs(i, j):
    if out_of_bounds or grid[i][j] == "0":
        return
    grid[i][j] = "0"
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j + 1)
    dfs(i, j - 1)

This logic is identical to flood fill: stop at boundaries, mark visited cells, and explore neighbors.

Why This Approach Works

• Each cell is visited only once
• Connected land cells are grouped together
• Each DFS call corresponds to exactly one island

The time complexity is O(rows × columns), since every cell is processed once. The space complexity is also O(rows × columns) in the worst case due to the recursion stack.

Complete Implementation

class Solution:
    def visit_cell(self, i, j, size):
        if i < 0 or i > size[0] or j < 0 or j > size[1] or self.grid[i][j] == "0":
            return 

        self.grid[i][j] = "0"
        self.visit_cell(i+1, j, size)
        self.visit_cell(i, j+1, size)
        self.visit_cell(i-1, j, size)
        self.visit_cell(i, j-1, size)

    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        answer = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if self.grid[i][j] != "0":
                    self.visit_cell(i, j, (len(grid) - 1, len(grid[0]) - 1))
                    answer += 1
        return answer

Conclusion

The Number of Islands problem does not require an explicitly built graph. Instead, it relies on recognizing that a grid can behave like a graph and that flood fill is simply a form of graph traversal.

If you understand flood fill, you already understand DFS on a grid. This realization makes many grid-based problems much easier to approach.

Full source code is available here: https://github.com/RohitSingh-04/Python-Solutions/blob/main/LC200.py