How to Find the Number of Islands in a 2D Grid Using DFS or BFS

The most efficient way to count islands in a 2D grid is to iterate through each cell and trigger a graph traversal—either depth-first search (DFS) or breadth-first search (BFS)—whenever land is encountered, marking the entire connected component as visited to avoid double counting.

The kdn251/interviews repository provides a battle-tested implementation of the classic Number of Islands problem, demonstrating exactly how to find the number of islands in a 2D grid using DFS as the primary traversal strategy. This algorithm is a staple in technical interviews at major tech companies, with specific implementations available for Google, Facebook, and Amazon interview preparation. Understanding both DFS and BFS approaches ensures you can adapt the solution to constraints involving recursion depth or memory usage.

DFS Implementation from Source

The repository implements the island counting logic using an in-place modification strategy that "sinks" entire islands by flipping land cells to water during traversal.

Grid Traversal and Entry Point

In leetcode/depth-first-search/NumberOfIslands.java (lines 22-33), the public method numIslands stores a reference to the input grid and iterates through each row and column using nested loops. When the scan encounters a land cell ('1'), it invokes the recursive helper function sink and increments the island counter.

The Recursive Sink Function

The sink function defined at lines 41-57 performs the actual depth-first search. It first validates matrix boundaries and checks whether the current cell is water ('0'). If the cell contains valid land, the function marks it as water to prevent revisiting, then recursively explores all four orthogonal neighbors (up, down, left, right).

int sink(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
        return 0;
    }
    grid[i][j] = '0';
    sink(grid, i + 1, j);
    sink(grid, i - 1, j);
    sink(grid, i, j + 1);
    sink(grid, i, j - 1);
    return 1;
}

Island Counting Logic

As shown in lines 36-39 of the source file, each successful call to sink returns the integer 1, representing one fully explored island. The numIslands method accumulates these returns into a running total, yielding the final count after completing the full grid scan.

BFS Alternative Approach

While the kdn251/interviews repository focuses on the recursive DFS solution, you can implement the same logic iteratively using breadth-first search to avoid recursion stack limits on massive grids. Instead of recursive calls, push the starting coordinates onto a Queue<int[]>, then iteratively dequeue cells, mark them as '0', and enqueue valid land neighbors until the queue empties.

int bfs(char[][] grid, int i, int j) {
    Queue<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{i, j});
    grid[i][j] = '0';
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1];
        for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == '1') {
                grid[nr][nc] = '0';
                q.offer(new int[]{nr, nc});
            }
        }
    }
    return 1;
}

Company-Specific Interview Variations

The repository duplicates the core algorithm across multiple company-specific packages to illustrate how the same solution applies across different interview contexts. You can find identical DFS logic with minor stylistic variations in:

• company/google/NumberOfIslands.java
• company/facebook/NumberOfIslands.java
• company/amazon/NumberOfIslands.java

Each version maintains the same sink function signature and in-place marking strategy, demonstrating that the algorithm remains constant regardless of the interviewing company.

Complexity Analysis

Both DFS and BFS approaches run in O(m × n) time complexity, where m represents the number of rows and n represents the number of columns, since each cell is visited at most once. The space complexity is O(m × n) in the worst case, representing the maximum depth of the recursion stack for DFS or the maximum queue size for BFS when the entire grid consists of a single island.

Summary

• The numIslands method in NumberOfIslands.java iterates through the grid to locate unvisited land cells.
• The sink function uses recursive DFS to mark entire connected components as visited by flipping '1' to '0'.
• Each invocation of the traversal function increments the island counter by exactly one, ensuring accurate counting.
• BFS provides an iterative alternative using a queue to explore neighbors level by level, preventing stack overflow on large inputs.
• The solution achieves optimal O(m × n) time and space complexity while modifying the grid in-place.

Frequently Asked Questions

What is the difference between using DFS and BFS for the Number of Islands problem?

Both algorithms correctly count islands by exploring connected components, but DFS uses the call stack for traversal while BFS uses an explicit queue. DFS typically requires less boilerplate code and is the preferred implementation in the kdn251/interviews repository, whereas BFS avoids potential stack overflow errors on grids containing extremely large single islands.

Why does the solution mark visited islands as '0' instead of using a separate visited matrix?

Modifying the input grid in-place—referred to as "sinking" the island—reduces auxiliary space complexity from O(m × n) to O(1) excluding the recursion stack or queue storage. This optimization is standard in interview settings unless the problem explicitly prohibits mutating the input array.

How does the algorithm handle edge cases like empty grids or grids with no land?

The implementation safely handles empty inputs by checking grid dimensions before initiating traversal. If the grid is null, empty, or contains only water characters ('0'), the outer loops complete without invoking sink, correctly returning a count of zero islands.

Where can I find the complete source code for this solution?

The primary Java implementation resides in the kdn251/interviews repository at leetcode/depth-first-search/NumberOfIslands.java, with additional interview-specific versions available in the company/google, company/facebook, and company/amazon directories for targeted preparation.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}