Island Counting Pattern in Grid Problems: A Complete DFS Guide

The island counting pattern uses depth-first search (DFS) to identify and mark connected land cells in a 2D grid, counting each distinct group of adjacent '1's as one island.

This pattern is a fundamental algorithmic technique for solving matrix traversal problems, prominently featured in the azl397985856/leetcode repository. By treating land cells as nodes and adjacency as edges, the pattern efficiently identifies connected components in binary grids.

How the Island Counting Pattern Works

The algorithm follows a systematic approach to explore the entire grid while tracking distinct land masses.

Conceptual Flow

1. Scan the grid systematically, examining each cell from top-left to bottom-right.
2. Trigger DFS whenever an unvisited land cell ('1') is encountered.
3. Mark visited cells during the DFS traversal to prevent recounting.
4. Increment counter after the DFS completes, indicating one full island has been explored.
5. Continue scanning until all cells are processed.

Why DFS Works for Island Counting

DFS is optimal for this pattern because it naturally traverses all cells belonging to the same connected component before backtracking. This guarantees that each island is counted exactly once. The algorithm can be implemented in-place by overwriting visited land cells with water ('0'), eliminating the need for an auxiliary visited array and reducing space complexity to O(1) excluding the recursion stack.

In-Place DFS Implementation

The azl397985856/leetcode repository provides concrete implementations in multiple languages. The key technique involves marking cells as visited by flipping '1' to '0' during traversal.

Python Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            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'                     # mark as visited

            dfs(r + 1, c)                        # down

            dfs(r - 1, c)                        # up

            dfs(r, c + 1)                        # right

            dfs(r, c - 1)                        # left

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

JavaScript Solution

function dfs(grid, r, c, rows, cols) {
  if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;
  grid[r][c] = '0';
  dfs(grid, r + 1, c, rows, cols);
  dfs(grid, r - 1, c, rows, cols);
  dfs(grid, r, c + 1, rows, cols);
  dfs(grid, r, c - 1, rows, cols);
}

var numIslands = function(grid) {
  let islands = 0;
  const rows = grid.length;
  if (!rows) return 0;
  const cols = grid[0].length;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === '1') {
        dfs(grid, i, j, rows, cols);
        islands++;
      }
    }
  }
  return islands;
};

Both implementations follow the four-directional adjacency model (up, down, left, right) and use the grid itself to track visited status, aligning with the pattern described in thinkings/island.en.md.

Complexity Analysis

Understanding the computational bounds of the island counting pattern is crucial for optimizing grid-based solutions.

Time Complexity

Each cell is visited at most once during the entire algorithm. When a DFS is triggered, it explores all connected land cells, but once marked as '0', those cells are never processed again. Therefore, the time complexity is O(m × n) where m is the number of rows and n is the number of columns.

Space Complexity

The in-place modification approach uses O(1) extra space excluding the recursion stack. The recursion depth depends on the maximum size of an island. In the worst case (all cells are land), the recursion stack could grow to O(m × n). For grids with large islands, an iterative BFS approach with an explicit queue might be preferred to control memory usage.

Source Code References

The azl397985856/leetcode repository provides comprehensive resources for mastering this pattern:

• thinkings/island.en.md — Conceptual overview, generic DFS template, and extensions including perimeter calculation and region counting.
• problems/200.number-of-islands.md — Full problem statement for LeetCode 200, multiple language solutions, and detailed complexity analysis.
• assets/problems/200.number-of-islands.jpg — Visual illustration demonstrating island identification in sample grids.

Summary

• The island counting pattern identifies connected components in binary grids using DFS traversal.
• Four-directional adjacency (up, down, left, right) defines connectivity between land cells.
• In-place marking by flipping '1' to '0' eliminates the need for a separate visited array, achieving O(1) auxiliary space.
• The algorithm runs in O(m × n) time, visiting each cell exactly once.
• This pattern extends to variations including perimeter calculation, maximum island area, and closed island detection.

Frequently Asked Questions

What is the island counting pattern in grid problems?

The island counting pattern is an algorithmic technique that uses depth-first search or breadth-first search to count distinct groups of connected land cells in a 2D binary grid. Each group of horizontally or vertically adjacent '1' cells constitutes one island. The pattern systematically scans the grid, initiates a traversal from each unvisited land cell, marks all reachable cells as visited, and increments a counter for each traversal initiated.

Can BFS be used instead of DFS for island counting?

Yes, breadth-first search is equally valid for the island counting pattern. While DFS uses the call stack for recursion (or an explicit stack for iteration), BFS uses a queue to explore cells level by level. Both approaches correctly identify connected components and achieve the same O(m × n) time complexity. BFS may be preferred when the grid contains extremely large islands that could cause stack overflow with recursive DFS, as the queue size is bounded by the grid dimensions rather than recursion depth.

How do you handle diagonal adjacency in island counting?

Standard island counting problems consider only four-directional adjacency (up, down, left, right). To support eight-directional connectivity including diagonals, modify the DFS or BFS traversal to check all eight neighboring cells: (r-1,c-1), (r-1,c), (r-1,c+1), (r,c-1), (r,c+1), (r+1,c-1), (r+1,c), (r+1,c+1). The core logic remains identical—mark visited cells and count distinct traversals—but the connectivity definition changes from 4-directional to 8-directional adjacency.

What is the space complexity when using a separate visited array?

When using an auxiliary visited array instead of in-place modification, the space complexity becomes O(m × n) to store the boolean visitation status of every cell. This approach is necessary when the original grid cannot be modified (e.g., immutable input or multi-pass algorithms requiring original values). The recursion stack still adds up to O(m × n) in the worst case, making the total auxiliary space O(m × n). For space-constrained environments, the in-place marking technique (O(1) extra space excluding stack) is strongly preferred.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}