Grid Traversal: BFS and DFS for Island Problems

1. From Adjacency Lists to Grids: The Implicit Graph

So far, we've worked with graphs defined explicitly by adjacency lists. However, many interview problems present graphs implicitly. A 2D grid is the most common example.

Think of it this way:

• Nodes: Each cell (r, c) in the grid is a node.
• Edges: An edge exists between two cells if they are "adjacent" and satisfy a certain condition (e.g., both are land). In most problems, adjacency is defined as sharing a side (horizontally or vertically), but sometimes it includes diagonals.

The key is that you don't need to build an adjacency list first. You can compute the neighbors of any given cell (r, c) on the fly: (r-1, c), (r+1, c), (r, c-1), and (r, c+1). This is the core idea behind applying graph traversals to grids.

2. The 'Number of Islands' Problem

The canonical problem for this pattern is "Number of Islands" (LeetCode 200), a favorite at companies like Google and Amazon. You're given a 2D grid where '1's represent land and '0's represent water. Your task is to count the number of distinct islands. An island is a group of '1's connected horizontally or vertically.

To get a feel for the problem and the intuitive approach, watch the beginning of this excellent video from NeetCode.

3. The General Strategy: Counting Connected Components

As you saw in the video, the problem boils down to finding and counting "connected components" in the grid-graph. This gives us a universal template that works with either DFS or BFS.

The pattern is:

1. Initialize an islands_count to 0.
2. Create a way to track visited cells to avoid recounting. A 2D boolean array or a set of (row, col) tuples works well.
3. Iterate through every cell (r, c) in the grid.
4. If the current cell (r, c) is land ('1') and has not been visited yet:
   • You've discovered a new island! Increment islands_count.
   • Launch a graph traversal (DFS or BFS) starting from (r, c).
   • This traversal's job is to find every piece of land connected to (r, c) and mark it as visited. This effectively "sinks" the entire island, ensuring you don't count any part of it again.
5. After iterating through all cells, return islands_count.

This "iterate and flood-fill" approach is a fundamental pattern for many grid problems.

4. Implementation with Depth-First Search (DFS)

DFS is a natural fit for this problem, as its recursive nature makes for clean and concise code. When we find an unvisited '1', we'll start a recursive dfs function that explores that island to its "dead ends" before backtracking.

This video provides a fantastic step-by-step implementation using a recursive DFS.

Let's break down the dfs helper function's logic:

def dfs(grid, r, c):
    # 1. Base cases for stopping the recursion:
    # - Out of bounds
    # - Current cell is water
    if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] == '0':
        return

    # 2. Mark as visited to prevent infinite loops and re-counting.
    # Here, we modify the grid in-place.
    grid[r][c] = '0' 

    # 3. Recursive step: visit all 4 neighbors
    dfs(grid, r + 1, c) # Down
    dfs(grid, r - 1, c) # Up
    dfs(grid, r, c + 1) # Right
    dfs(grid, r, c - 1) # Left

A note on marking visited cells:

• In-place modification: Changing '1' to '0' (or '#') is space-efficient ($O(1)$ extra space, besides the recursion stack) and common in competitive programming and interviews. The downside is that it mutates the input grid.
• Auxiliary visited set/matrix: Using a separate visited set or boolean matrix (e.g., visited.add((r, c))) is cleaner, as it doesn't modify the input. This uses $O(M\times N)$ extra space.

For an interview, you can mention both and ask if modifying the input is acceptable.

5. Implementation with Breadth-First Search (BFS)

We can just as easily use BFS for the traversal part. Instead of a deep recursive dive, BFS will explore the island layer by layer using a queue. The main for-loop structure for iterating through the grid remains identical.

The NeetCode video you started earlier continues by implementing the BFS solution.

The BFS helper logic looks like this:

from collections import deque

def bfs(grid, r, c, visited):
    q = deque([(r, c)])
    visited.add((r, c))
    
    while q:
        row, col = q.popleft()
        
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            
            # Check if neighbor is valid and unvisited
            if (nr in range(len(grid)) and
                nc in range(len(grid[0])) and
                grid[nr][nc] == '1' and
                (nr, nc) not in visited):
                
                q.append((nr, nc))
                visited.add((nr, nc))

6. Complexity and Final Comparison

For an $M\times N$ grid:

• Time Complexity: $O(M\times N)$

  • Both DFS and BFS solutions require traversing the entire grid once with the outer loops. The inner traversals (DFS/BFS) will visit each '1' cell exactly once across the entire execution. Therefore, the total time is proportional to the number of cells.

• Space Complexity: $O(M\times N)$ in the worst case

  • BFS: The maximum size of the queue determines the space. In a worst-case scenario (like a checkerboard), the queue could hold roughly half the cells.
  • DFS (recursive): The space is determined by the maximum depth of the recursion stack. The worst case is a single, long, snake-like island that winds through the entire grid, leading to a recursion depth of $O(M\times N)$.
  • Note: If you use an auxiliary visited matrix/set, that also contributes $O(M\times N)$ to the space complexity.

For this problem, both DFS and BFS are perfectly valid. The choice is often a matter of style.

A Note on Variations: The classic "Number of Islands" problem considers 4-directional adjacency. Some variations may define islands by including diagonal connections (8-directional). The only change to your code would be to expand the directions array to include (1, 1), (1, -1), (-1, 1), and (-1, -1). The "Number of Islands" article from GeeksForGeeks (LINK) provides a clear example of an 8-directional implementation if you're curious.

Conclusion

Congratulations! You've successfully applied your knowledge of graph traversals to a new and important problem domain. Grid problems are extremely common in interviews, and the "Number of Islands" pattern is a gateway to solving many of them.

Key Takeaways:

• Grids are Implicit Graphs: You can perform graph traversals on them by calculating neighbors on the fly.
• Count Connected Components: The core strategy for "Number of Islands" is to iterate through each cell and launch a traversal (DFS or BFS) for any unvisited component, incrementing a counter each time.
• Sink the Island: The traversal's main job is to find all parts of the current island and mark them as visited so they aren't counted again.
• DFS vs. BFS: Both work and have the same time complexity. DFS can be more concise recursively, while BFS is always iterative and can be better for finding shortest paths in grids (a topic for another day!).

Preview of the Next Lesson:

So far, we've only dealt with unweighted graphs, where every edge has the same "cost". In the next lesson, we'll level up by tackling weighted graphs. You will implement Dijkstra's algorithm to find the shortest path in a weighted graph, a cornerstone algorithm with countless real-world applications.