Problem Description

You are given a 2D grid of size m x n where each cell contains either '1' (representing land) or '0' (representing water). Your task is to count the total number of islands in this grid.

An island is defined as a group of adjacent land cells ('1's) that are connected horizontally or vertically. Diagonal connections don't count - only cells that share an edge are considered connected. Each island is completely surrounded by water ('0's).

The entire grid is surrounded by water on all four edges (you can assume there's water beyond the grid boundaries).

For example, if you have a grid like:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

This grid contains 3 islands:

• Island 1: The connected '1's in the top-left corner (2x2 block)
• Island 2: The single '1' in the middle
• Island 3: The two connected '1's in the bottom-right

The solution uses Depth-First Search (DFS) to traverse each island. When a '1' is found, it triggers a DFS that marks all connected land cells as visited (by changing them to '0'), effectively "sinking" the entire island. Each time a new unvisited '1' is found in the main loop, it represents a new island, so the counter is incremented. The dirs array (-1, 0, 1, 0, -1) is used with pairwise to generate the four directional movements: up (-1, 0), right (0, 1), down (1, 0), and left (0, -1).

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The 2D grid can be viewed as a graph where each cell is a node, and adjacent cells (horizontally and vertically) are connected by edges. We need to find connected components of '1's.

Is it a tree?

• No: The problem is not about a tree structure. We have a general graph with potential cycles (multiple land cells can form various shapes).

Is the problem related to directed acyclic graphs?

• No: The connections between adjacent cells are undirected (if cell A is adjacent to cell B, then B is also adjacent to A).

Is the problem related to shortest paths?

• No: We're not finding shortest paths between nodes. We're counting the number of distinct connected components (islands).

Does the problem involve connectivity?

• Yes: The core of the problem is identifying connected components - groups of '1's that are connected horizontally or vertically.

Does the problem have small constraints?

• Yes: While the grid can be up to 300x300, we can afford to visit each cell, and the DFS approach is efficient enough for these constraints.

DFS/backtracking?

• Yes: DFS is perfect for exploring all cells in a connected component (island) and marking them as visited.

Conclusion: The flowchart suggests using DFS to solve this connectivity problem. DFS allows us to explore each island completely, marking all connected land cells as visited before moving on to find the next unvisited island.

Intuition

The key insight is to think of this problem as finding connected components in a graph. Each land cell ('1') is like a node, and two land cells are connected if they're adjacent horizontally or vertically.

When we encounter an unvisited land cell, we've discovered a new island. But how big is this island? We need to explore all land cells connected to it. This is where DFS comes in naturally - starting from one land cell, we want to visit all reachable land cells that form the same island.

The clever part is how we handle "visited" cells. Instead of maintaining a separate visited array, we can modify the grid itself - changing '1' to '0' as we visit each cell. This "sinks" the island as we explore it, preventing us from counting the same island multiple times.

The algorithm flow becomes simple:

1. Scan through the entire grid
2. When we find a '1', we've found a new island - increment our island counter
3. Use DFS to explore and "sink" the entire island by turning all connected '1's into '0's
4. Continue scanning - any '1' we find now must belong to a different island

The beauty of this approach is that each cell is visited at most twice - once during the main grid scan, and potentially once more during a DFS traversal. The DFS naturally handles islands of any shape or size, following the connections until all parts of an island are explored.

The dirs array pattern (-1, 0, 1, 0, -1) paired with pairwise is an elegant way to generate the four directions: consecutive pairs give us (-1, 0) for up, (0, 1) for right, (1, 0) for down, and (0, -1) for left.

Solution Approach

The implementation uses DFS to traverse and mark connected land cells. Let's walk through the solution step by step:

Main Algorithm Structure:

1. Initialize counters and dimensions:

   • ans = 0 to count islands
   • dirs = (-1, 0, 1, 0, -1) for direction vectors
   • m, n = len(grid), len(grid[0]) to get grid dimensions

2. DFS Helper Function:

   def dfs(i, j):
       grid[i][j] = '0'  # Mark current cell as visited (sink it)
       for a, b in pairwise(dirs):
           x, y = i + a, j + b
           if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
               dfs(x, y)

   The DFS function:

   • Takes coordinates (i, j) of a land cell
   • Immediately marks it as water '0' to prevent revisiting
   • Uses pairwise(dirs) to generate four direction pairs: (-1, 0), (0, 1), (1, 0), (0, -1)
   • For each direction, calculates new coordinates (x, y)
   • Checks if the new position is:
     • Within bounds: 0 <= x < m and 0 <= y < n
     • Is land: grid[x][y] == '1'
   • Recursively calls DFS on valid land neighbors

3. Main Loop:

   for i in range(m):
       for j in range(n):
           if grid[i][j] == '1':
               dfs(i, j)
               ans += 1

   • Iterates through every cell in the grid
   • When a '1' is found (unvisited land):
     • Calls dfs(i, j) to explore and sink the entire island
     • Increments the island counter
   • Since DFS converts all connected '1's to '0's, each island is counted exactly once

Data Structures Used:

• 2D Grid: Modified in-place to track visited cells
• Recursion Stack: Implicit stack used by DFS for traversal
• Direction Vector: Compact representation of four directions using pairwise

Time Complexity: O(m × n) where m and n are grid dimensions. Each cell is visited at most once.

Space Complexity: O(m × n) in worst case for the recursion stack (when the entire grid is one island).

The elegance of this solution lies in its simplicity - by modifying the grid in-place and using DFS to explore each island completely, we avoid the need for additional visited tracking structures while ensuring each island is counted exactly once.

Example Walkthrough

Let's trace through a small example to illustrate how the DFS solution works:

Given Grid:

1 1 0
0 1 0
1 0 1

Step-by-step Execution:

Initial State:

• ans = 0 (island counter)
• Start scanning from position (0,0)

Step 1: Found '1' at (0,0)

• This is unvisited land, so we found a new island!
• Call dfs(0, 0) to explore this island
• DFS exploration:

  • Mark (0,0) as '0' → Grid becomes:

    0 1 0
    0 1 0
    1 0 1

  • Check 4 directions from (0,0):

    • Up: out of bounds
    • Right: (0,1) is '1' → Call dfs(0, 1)
    • Down: (1,0) is '0' → Skip
    • Left: out of bounds

  • From (0,1), mark it as '0' → Grid becomes:

    0 0 0
    0 1 0
    1 0 1

  • Check 4 directions from (0,1):

    • Up: out of bounds
    • Right: (0,2) is '0' → Skip
    • Down: (1,1) is '1' → Call dfs(1, 1)
    • Left: (0,0) is '0' → Skip

  • From (1,1), mark it as '0' → Grid becomes:

    0 0 0
    0 0 0
    1 0 1

  • Check 4 directions from (1,1):

    • All neighbors are either '0' or out of bounds

  • DFS completes, returning to main loop

• Increment ans = 1

Step 2: Continue scanning

• (0,1) is '0' → Skip
• (0,2) is '0' → Skip
• (1,0) is '0' → Skip
• (1,1) is '0' → Skip
• (1,2) is '0' → Skip

Step 3: Found '1' at (2,0)

• This is unvisited land, new island found!
• Call dfs(2, 0)
• Mark (2,0) as '0' → Grid becomes:

  0 0 0
  0 0 0
  0 0 1

• Check 4 directions: all are '0' or out of bounds
• Increment ans = 2

Step 4: Continue scanning

• (2,1) is '0' → Skip

Step 5: Found '1' at (2,2)

• This is unvisited land, new island found!
• Call dfs(2, 2)
• Mark (2,2) as '0' → Grid becomes:

  0 0 0
  0 0 0
  0 0 0

• Check 4 directions: all are '0' or out of bounds
• Increment ans = 3

Final Result: ans = 3 islands

The key insight: Each time we find a '1' in the main loop, we've discovered a new island. The DFS ensures we explore and "sink" the entire island before continuing, preventing double-counting.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid.

• The outer loops iterate through every cell in the grid, which takes O(m * n) time.
• For each cell that contains '1', we perform a DFS traversal. In the worst case, if the entire grid is filled with '1's forming one large island, the DFS will visit every cell once.
• Each cell is visited at most twice: once by the outer loop iteration and potentially once during a DFS traversal from a neighboring cell.
• The pairwise function with dirs = (-1, 0, 1, 0, -1) generates 4 direction pairs: [(-1, 0), (0, 1), (1, 0), (0, -1)], representing up, right, down, and left movements. This operation is O(1) for each cell.
• Overall, every cell is processed a constant number of times, resulting in O(m * n) time complexity.

Space Complexity: O(m * n) in the worst case.

• The space complexity is dominated by the recursive call stack during DFS traversal.
• In the worst case, if the entire grid forms a single island with all cells containing '1', the DFS recursion depth could reach O(m * n) for a snake-like pattern that visits every cell sequentially.
• The dirs variable takes O(1) space.
• The algorithm modifies the input grid in-place by marking visited cells as '0', so no additional space is used for tracking visited cells.
• Therefore, the space complexity is O(m * n) due to the recursion stack.

Common Pitfalls

1. Modifying the Original Grid

Problem: The solution modifies the input grid in-place by changing '1's to '0's. This destroys the original data, which might be needed later or violates constraints if the grid should remain unchanged.

Example Scenario:

grid = [['1','1','0'], ['0','1','0']]
solution = Solution()
count = solution.numIslands(grid)
# grid is now [['0','0','0'], ['0','0','0']] - original data lost!

Solution: Create a separate visited tracking structure or make a deep copy:

def numIslands(self, grid: List[List[str]]) -> int:
    # Option 1: Use a visited set
    visited = set()
  
    def dfs(row, col):
        visited.add((row, col))
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            next_row, next_col = row + dr, col + dc
            if (0 <= next_row < rows and 
                0 <= next_col < cols and 
                grid[next_row][next_col] == '1' and
                (next_row, next_col) not in visited):
                dfs(next_row, next_col)
  
    # Option 2: Work with a copy
    grid_copy = [row[:] for row in grid]
    # Then use grid_copy in the original algorithm

2. Stack Overflow with Large Islands

Problem: For very large grids where one island covers most cells, the recursive DFS can cause stack overflow due to deep recursion.

Example: A 1000×1000 grid filled entirely with '1's would require recursion depth of up to 1,000,000.

Solution: Use iterative DFS with an explicit stack:

def dfs_iterative(row, col):
    stack = [(row, col)]
    while stack:
        curr_row, curr_col = stack.pop()
        if (curr_row < 0 or curr_row >= rows or 
            curr_col < 0 or curr_col >= cols or
            grid[curr_row][curr_col] != '1'):
            continue
      
        grid[curr_row][curr_col] = '0'
      
        # Add all 4 neighbors to stack
        stack.extend([(curr_row-1, curr_col), (curr_row+1, curr_col),
                     (curr_row, curr_col-1), (curr_row, curr_col+1)])

3. Type Confusion with Grid Values

Problem: Mixing string '1'/'0' with integer 1/0 comparisons, leading to subtle bugs.

Example:

# Wrong - comparing string with integer
if grid[row][col] == 1:  # This will always be False!
    dfs(row, col)

# Correct
if grid[row][col] == '1':
    dfs(row, col)

Solution: Be consistent with data types and consider converting at the start:

# Convert to integers if needed for consistency
grid = [[int(cell) for cell in row] for row in grid]
# Then use integer comparisons throughout

4. Incorrect Boundary Checking Order

Problem: Accessing grid elements before checking boundaries causes IndexError.

Example:

# Wrong - accesses grid before boundary check
if grid[next_row][next_col] == '1' and 0 <= next_row < rows:
    dfs(next_row, next_col)  # IndexError if next_row is out of bounds!

# Correct - check boundaries first
if 0 <= next_row < rows and 0 <= next_col < cols and grid[next_row][next_col] == '1':
    dfs(next_row, next_col)

Solution: Always validate indices before accessing array elements, using short-circuit evaluation.