Leetcode 200. Number of Islands

Let's understand what we're being asked to do. We have a 2D grid (matrix) filled with '0's and '1's, like:

[
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

We need to count how many islands exist. An island is a group of '1's connected horizontally or vertically (not diagonally). In the example above, there are 3 islands: the top-left 2×2 block, the single '1' in the middle, and the bottom-right 1×2 block.

Important constraint: Connections are only 4-directional (up, down, left, right). Diagonal connections don't count!

Edge cases to consider: What if the grid is empty? What if the entire grid is water ('0's)? What if the entire grid is one giant island? What if islands touch at corners but aren't connected?

When we find a '1' that hasn't been visited yet, we've discovered a new island. But that '1' might be part of a larger connected group.

The key insight: once we find an unvisited '1', we need to explore all connected '1's to mark the entire island as visited. This prevents counting the same island multiple times.

By exploring all connected cells when we discover a new island, we ensure each island is counted exactly once.

This transforms the problem from 'count all '1's' (which would be wrong) to 'count connected components' (which is correct). The difference is between counting individual cells vs. counting groups of connected cells.

Imagine you're looking at a map of actual islands from an airplane. When you spot land, you don't just mark that one spot - you trace the entire coastline to understand the full extent of that island.

Similarly, when we find a '1', we need to 'flood fill' outward in all 4 directions, marking every connected '1' as part of the same island. Only after fully exploring one island do we continue searching for the next one.

The optimal approach uses Depth-First Search (DFS) to explore connected components. Iterate through each cell in the grid. When we find an unvisited '1', increment the island count and launch a DFS to mark all connected '1's as visited (by changing them to '0' or using a separate visited set). The DFS explores all 4 directions recursively, ensuring the entire island is marked before continuing the search. This guarantees each island is counted exactly once.

def num_islands(grid):
    """
    Count number of islands using DFS.
    Time: O(m*n), Space: O(m*n) for recursion stack.
    """
    if not grid or not grid[0]:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    island_count = 0
    
    def dfs(r, c):
        # Base case: out of bounds or water/visited
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        
        # Mark current cell as visited by changing to '0'
        grid[r][c] = '0'
        
        # Explore all 4 directions
        dfs(r + 1, c)  # down
        dfs(r - 1, c)  # up
        dfs(r, c + 1)  # right
        dfs(r, c - 1)  # left
    
    # Iterate through each cell in grid
    for row in range(rows):
        for col in range(cols):
            # Found unvisited land - new island
            if grid[row][col] == '1':
                island_count += 1
                # Mark entire island as visited
                dfs(row, col)
    
    return island_count

• DFS/BFS for connected components: When you need to find groups of connected cells in a matrix (islands, regions, clusters), Depth-First Search or Breadth-First Search is the go-to pattern - it systematically explores all reachable cells from a starting point, naturally identifying one complete component per search.
• In-place marking technique: Instead of maintaining a separate visited set (which costs O(mn) space), modify the grid directly by changing '1' to '0' (or another marker) as you visit cells - this achieves O(1) auxiliary space while preventing revisits and double-counting islands.
• Four-directional traversal pattern: Implement neighbor exploration using direction arrays like `[(0,1), (1,0), (0,-1), (-1,0)]` or explicit checks - this makes the code cleaner and easier to extend to 8-directional or other connectivity patterns in similar problems.
• Boundary validation before recursion: Always check bounds (row/col within grid) AND cell value ('1' for land) before making recursive DFS calls or adding to BFS queue - failing to validate boundaries first leads to index-out-of-bounds errors, while checking cell value prevents infinite loops.
• Linear time complexity insight: The O(mn) time complexity works because each cell is visited at most once - once marked as visited (turned to '0'), it's never processed again, making this approach optimal since you must examine every cell at least once to count all islands.
• Flood-fill pattern recognition: This problem is fundamentally a flood-fill algorithm (like paint bucket in image editors) - recognize this pattern in problems involving region detection, image segmentation, maze solving, or any scenario where you need to identify contiguous groups in a 2D space.