PrepKitBeta
DSA›Matrix/Grid Patterns (2D)›Grid as Graph

Grid as Graph

Matrix/Grid Patterns (2D)

The trick isn’t learning a new algorithm—it’s seeing an old one in a new form.

You've mastered traversing trees and graphs. But what happens when the graph is hidden? Many problems present a grid or a maze, and the key is to see it not as a matrix, but as a graph in disguise.

Problem: Number of Islands (LeetCode Link): Given an m x n 2D grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. 💡 Hint

The Grid is an Implicit Graph

This is the fundamental insight for a huge category of problems. A grid can be viewed as a graph where:

  • Nodes: Each cell (r, c) is a node.
  • Edges: An edge exists between a cell and its adjacent neighbors (up, down, left, right).

Since you already know graph traversal algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS), the challenge isn't learning a new algorithm, but learning how to adapt those algorithms to the grid's implicit structure.

Adapting Traversal to a Grid

There are a few key implementation details you must handle when running a traversal on a grid.

1. The Main Loop

Your traversal algorithm (like dfs or bfs) will explore a single connected component (a single island). To find all components, you need a main loop that iterates through every cell, acting as a starting point.

# Main loop to find all islands
count = 0
for r in range(ROWS):
    for c in range(COLS):
        if grid[r][c] == '1':
            # Found the start of a new island
            count += 1
            # Launch a traversal to find and sink the rest of it
            dfs(grid, r, c)

2. Boundary Checking

Unlike an explicit graph where neighbors are given, in a grid, you must calculate them. This means you must always check if a calculated neighbor (new_r, new_c) is within the valid grid boundaries before accessing it.

# Inside your DFS/BFS traversal
def is_valid(r, c):
    return 0 <= r < ROWS and 0 <= c < COLS

# Before recursing or adding to queue:
if is_valid(new_r, new_c) and ...:
    # continue

3. Tracking Visited Nodes

You must keep track of visited cells to avoid infinite loops and recounting parts of an island. There are two common ways to do this:

  • In-Place Modification (Preferred): If the problem allows, modify the grid directly. When you visit a land cell '1', change it to '0', '#', or another character. This is O(1)O(1) space.
  • Auxiliary visited Matrix: Create a separate boolean matrix of the same dimensions, visited[r][c], initialized to false. This uses O(M∗N)O(M*N) extra space but is necessary if you cannot modify the input grid.

Walkthrough: Solving "Number of Islands"

Let's combine these ideas to solve the problem using an in-place DFS.

  1. Main Loop: Iterate through every cell (r, c).
  2. Find Land: If grid[r][c] is '1', we've found a new, unvisited island. Increment the island counter.
  3. Launch DFS: Call dfs(r, c) to explore and "sink" this entire island by changing all its '1's to '0's.
  4. DFS Logic:
    • Base Cases: The traversal stops if the current cell is out of bounds or is water ('0').
    • Mark as Visited: Set grid[r][c] = '0'.
    • Explore Neighbors: Recursively call dfs for all four adjacent cells.
def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    islands = 0
    
    def dfs(r, c):
        # Base cases for stopping the recursion
        if not (0 <= r < rows and 0 <= c < cols and grid[r][c] == '1'):
            return
        
        grid[r][c] = '0' # Mark as visited (in-place)
        
        # Explore neighbors
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

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

Complexity Analysis

  • Time Complexity: O(M∗N)O(M * N), where M is the number of rows and N is the number of columns. Each cell is visited exactly once.
  • Space Complexity: O(M∗N)O(M * N) in the worst case. The space is used by the recursion stack. In the worst case, the grid is all land, and the recursion depth can go up to M * N.

More Problems & Variations

  1. Max Area of Island (LeetCode Link): Instead of just counting islands, find the size of the largest one. 💡 Hint
  2. Rotting Oranges (LeetCode Link): Find the minimum time for all fresh oranges to become rotten. 💡 Hint
  3. 01 Matrix (LeetCode Link): For each cell, find the distance to the nearest 0. 💡 Hint
  4. Flood Fill (LeetCode Link): Given a starting pixel, change its color and all connected pixels of the same original color to a new color. 💡 Hint

Bonus Point: Distributed Systems

In large-scale systems like databases or cloud clusters, availability zones can be modeled as nodes in a grid. When failures occur, the real question becomes: “Which parts of the system are still connected?” That’s an island-counting problem, exactly what you just solved. Graph thinking isn’t just for mazes. It’s how resilient systems survive in production.

Back to Course