Grid as Graph

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. 💡 HintYou already know how to find connected components in a graph. How do you apply that knowledge here?

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) 

// Main loop to find all islands
int count = 0;
for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        if (grid[r][c] == '1') {
            // Found the start of a new island
            count++;
            // Launch a traversal to find and sink the rest of it
            dfs(grid, r, c);
        }
    }
}

// Main loop to find all islands
int count = 0;
for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
        if (grid[r][c] == '1') {
            // Found the start of a new island
            count++;
            // 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

// Inside your DFS/BFS traversal
boolean isValid(int r, int c) {
    return r >= 0 && r < rows && c >= 0 && c < cols;
}
// Before recursing or adding to queue:
if (isValid(new_r, new_c) && ...) {
    // continue
}

// Inside your DFS/BFS traversal
bool isValid(int r, int c) {
    return r >= 0 && r < rows && c >= 0 && c < cols
}
// Before recursing or adding to queue:
if (isValid(new_r, new_c) && ...) {
    // 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)$ space.
• Auxiliary visited Matrix: Create a separate boolean matrix of the same dimensions, visited[r][c], initialized to false. This uses $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

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    
    int rows = grid.length;
    int cols = grid[0].length;
    int islands = 0;
    
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                islands++;
                dfs(grid, r, c);
            }
        }
    }
    return islands;
}

private void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0') {
        return;
    }
    
    grid[r][c] = '0'; // Mark as visited
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

void dfs(vector<vector<char>>& grid, int r, int c) {
    if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == '0') {
        return;
    }
    
    grid[r][c] = '0'; // Mark as visited
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int rows = grid.size();
    int cols = grid[0].size();
    int islands = 0;
    
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == '1') {
                islands++;
                dfs(grid, r, c);
            }
        }
    }
    return islands;
}

Complexity Analysis

• Time Complexity: $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)$ 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. 💡 HintYour traversal function should return the size of the component it just explored. Keep track of the maximum size seen.
2. Rotting Oranges (LeetCode Link): Find the minimum time for all fresh oranges to become rotten. 💡 HintYou can also use a multi-source BFS where you start from all rotten oranges at once.
3. 01 Matrix (LeetCode Link): For each cell, find the distance to the nearest 0. 💡 HintThis is another BFS shortest path problem. It's a "multi-source" BFS where you should initialize the queue with all the '0' cells at once.
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. 💡 HintThis is similar to the "paint bucket" tool in graphics software. Use BFS or DFS to explore all connected pixels.

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.