Counting Connected Components in a Grid

Welcome to the next lesson in our module on Graph Modeling and Traversal. In our last session, we mastered Depth-First Search (DFS), the "adventurous explorer" of graph algorithms that dives deep into a path before backtracking. We saw how recursion provides a natural implementation and why a visited set is crucial for handling cycles.

Today, we'll apply this knowledge to a classic and highly practical interview problem pattern: analyzing grids. You'll learn to see a simple 2D grid not just as a matrix, but as an implicit graph. By the end of this lesson, you will be able to solve problems like "Number of Islands" by treating neighboring cells as graph edges and using a traversal algorithm to count connected components.

From Matrix to Graph: A Shift in Perspective

Many algorithm problems are presented in the form of a grid or matrix. The key insight that unlocks these problems is realizing that a grid is a graph in disguise.

• Nodes: Each cell (row, col) in the grid is a node.
• Edges: The edges are not stored in an adjacency list but are implicit. An edge exists between two cells if they are adjacent (e.g., horizontally or vertically) and meet certain criteria (e.g., both are 'land').

This is a powerful mental model. Instead of looking up a node's neighbors in a Map, you compute them on the fly by adding offsets to the current cell's coordinates.

The article "Graph Traversal on a Grid" from Levelop explains this concept beautifully.

As you've just read, the typical adjacency rule for a 4-directional grid can be captured in a simple array of offsets. In TypeScript, this looks like:

const DIRECTIONS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // Up, Down, Left, Right

// For a cell (r, c), a neighbor (nr, nc) is calculated as:
for (const [dr, dc] of DIRECTIONS) {
    const nr = r + dr;
    const nc = c + dc;
    // ... then check if (nr, nc) is valid and within bounds.
}

With this simple mechanism, we can now unleash our graph traversal algorithms on any grid.

Counting Islands: Finding Connected Components

The "Number of Islands" problem is a classic application of this grid-as-a-graph concept. You're given a grid of '1's (land) and '0's (water), and you need to count how many distinct islands exist. An island is a group of '1's connected horizontally or vertically.

This is exactly the graph problem of counting connected components.

The general algorithm for counting connected components in any graph is as follows:

1. Initialize a count to 0.
2. Iterate through every node in the graph.
3. If you find a node that you haven't visited yet:
   a. You've found a new component, so increment count.
   b. Start a graph traversal (like DFS or BFS) from this node.
   c. The traversal will explore and mark every node belonging to this component as 'visited'.
4. When the main iteration continues, it will skip over the now-visited nodes of the component you just explored, preventing you from counting them again.

Translating this to our grid problem:

1. Initialize islandCount = 0.
2. Loop through every cell (r, c) in the grid.
3. If the cell (r, c) is a '1' (land) and we haven't visited it:
   a. We've found a new island! Increment islandCount.
   b. Start a DFS from (r, c). This DFS will "sink" the island by visiting all connected '1's and marking them as visited.

The article "200. Number of Islands" from Algo.monster provides an excellent walkthrough of this logic.

Implementing the Solution

Now let's bring this all together in code. We need two main parts:

1. A main function that iterates through the grid.
2. A recursive DFS helper that explores an island from a starting cell.

A key implementation detail is how we handle the "visited" set. There are two common approaches:

• A separate Set: You can maintain a Set<string> where you store the coordinates of visited cells, e.g., "row,col". This is clean and doesn't modify the input.
• In-place modification: A common interview trick is to modify the grid directly. When you visit a land cell '1', you change it to something else (like '0' or '#') to mark it as visited. This saves space but modifies the input, which is something you should always state explicitly in an interview.

The video "Number of Islands - LeetCode 200 - JavaScript" by AlgoJS provides a clear, step-by-step implementation using recursive DFS and the in-place modification technique.

Here is the TypeScript implementation based on the logic from the video and the Algo.monster article. This structure is a powerful template for many grid-based traversal problems.

function numIslands(grid: string[][]): number {
    if (!grid || grid.length === 0) {
        return 0;
    }

    const rows = grid.length;
    const cols = grid[0].length;
    let islandCount = 0;

    // The recursive helper function to explore an island
    function dfs(r: number, c: number): void {
        // Base Cases for stopping the recursion:
        // 1. Out of bounds (row)
        // 2. Out of bounds (col)
        // 3. Current cell is water (or already visited)
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
            return;
        }

        // Mark the current cell as visited by "sinking" it
        grid[r][c] = '0';

        // Explore all 4 neighbors recursively
        dfs(r + 1, c); // Down
        dfs(r - 1, c); // Up
        dfs(r, c + 1); // Right
        dfs(r, c - 1); // Left
    }

    // Main loop to find new islands
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            // If we find a land cell, we've found the start of a new island
            if (grid[r][c] === '1') {
                islandCount++;
                // Start DFS to find and sink all parts of this island
                dfs(r, c);
            }
        }
    }

    return islandCount;
}

Complexity and Practical Considerations

Since you have an extensive background in development, it's important to consider the practical limits of this recursive solution.

• Time Complexity: $O(R\times C)$, where $R$ is the number of rows and $C$ is the number of columns. The nested loops iterate through each of the $R\times C$ cells, and the DFS traversal visits each land cell at most once. Therefore, every cell is processed a small, constant number of times.

• Space Complexity: $O(R\times C)$ in the worst case. This space is not used by an explicit data structure, but by the recursion call stack. Imagine a grid where the entire land mass is a single, long, snake-like path. The recursion could go as deep as the number of cells in the grid, potentially causing a stack overflow error.

For typical interview-sized grids, this recursive approach is usually fine. However, in a production system with very large grids, you would convert the recursive DFS to an iterative one using an explicit stack, which avoids the call stack limit. This is a point worth mentioning in an interview to demonstrate your practical knowledge.

The Levelop article also warns about this.

Conclusion

In this lesson, you've bridged the gap between abstract graph traversal and concrete grid problems. This is a significant step in your algorithmic journey, as this pattern appears frequently in various forms.

Key Takeaways:

• Grids as Implicit Graphs: The most crucial concept is viewing a grid's cells as nodes and adjacency as implicit edges defined by coordinate arithmetic.
• Counting Islands as Connected Components: The "Number of Islands" problem is a direct application of the standard algorithm for counting connected components in a graph.
• The Master Algorithm: The solution involves a nested loop over the grid to find starting points of unvisited components, and a traversal (like DFS) to explore and mark each component.
• Practical Trade-offs: You learned about the two ways to track visited nodes (separate set vs. in-place mutation) and the risk of stack overflow with deep recursion, which can be mitigated with an iterative approach.

In our next lesson, we will continue to use traversal algorithms to uncover properties of graphs. We will focus on a fundamental problem: detecting cycles in a graph, which requires a slight but important modification to our standard DFS.