Number of Islands: Grid DFS Pattern

Learning Outcome

After this lesson, you should be able to convert a grid into graph thinking and use DFS to mark one island at a time.

Problem Statement

Given a grid of land cells 1 and water cells 0, count how many groups of horizontally or vertically connected land exist.

Brute Force Approach

Compare every land cell with every other land cell to discover groups. This ignores locality and becomes unnecessarily slow.

Optimized Approach

Scan the grid once. When land is found, increment the count and DFS through its four-direction neighbors to mark that island.

Exact Pseudocode

count = 0
for each cell in grid:
  if cell is land:
    count += 1
    dfs(cell)
return count

dfs(row, col):
  if row or col is out of bounds:
    return
  if cell is water:
    return
  mark cell as water
  dfs four neighbors
  

Reference Code

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols or grid[r][c] != "1":
                return
            grid[r][c] = "0"
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

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

Sample Dry Run

Complexity

Edge Cases

• Diagonal land is not connected unless the prompt says so.
• An all-water grid returns 0.
• A single large island can create deep recursion.

Interview Checklist

• Use four directions only.
• Mark visited before exploring neighbors.
• Do not count the same island twice.

FAQs