Find the Total Number of Islands Using DFS

Given a binary grid where 1 represents land and 0 represents water, counting the total number of islands means counting distinct connected components of land cells.

This is LeetCode problem 200 and one of the most frequently tested graph problems in placement coding rounds.

Problem Statement

You receive an M × N grid. Each cell holds either 1 (land) or 0 (water). Two land cells are connected if they share a horizontal or vertical edge. An island is a maximal group of connected land cells. Return the count of islands.

Worked Example

Consider a 4 × 5 grid:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

• Cells (0,0), (0,1), (1,0), (1,1) form island 1.
• Cell (2,2) forms island 2 (no adjacent land neighbours).
• Cells (3,3) and (3,4) form island 3.

Total islands: 3.

DFS Approach: Grid Coloring

The algorithm iterates through every cell. When it encounters an unvisited 1, it launches a DFS that marks all reachable land as 0 (visited). Each launch corresponds to one new island.

Algorithm Steps

• Initialise count = 0.
• For each cell (r, c) in the grid:
  • If grid[r][c] == 1:
    • Increment count.
    • Call dfs(grid, r, c) to mark all connected land as 0.
• Return count.

DFS Helper

The recursive DFS for cell (r, c):

• If r or c is out of bounds, return.
• If grid[r][c] == 0, return.
• Set grid[r][c] = 0.
• Recurse on four neighbours: (r-1, c), (r+1, c), (r, c-1), (r, c+1).

Tracing Through the Example

Starting at (0,0):

• grid[0][0] is 1. Increment count to 1. Launch DFS.
• DFS visits (0,0), sets it to 0, recurses to (0,1) and (1,0).
• (0,1) sets to 0, tries (0,2) which is already 0.
• (1,0) sets to 0, recurses to (1,1).
• (1,1) sets to 0. All neighbours are now 0. DFS returns.

Continue scanning. Next unvisited 1 is at (2,2):

• Increment count to 2. DFS marks (2,2) as 0. No adjacent 1s.

Next unvisited 1 is at (3,3):

• Increment count to 3. DFS marks (3,3) and (3,4) as 0.

Final answer: 3.

Code Implementations

C++

#include <vector>
using namespace std;

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int rows = grid.size();
        int cols = grid[0].size();
        if (r < 0 || c < 0 || r >= rows || c >= cols) return;
        if (grid[r][c] == '0') return;
        grid[r][c] = '0';
        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 count = 0;
        for (int r = 0; r < grid.size(); r++) {
            for (int c = 0; c < grid[0].size(); c++) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }
};

Java

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

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

Python

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        if grid[r][c] == '0':
            return
        grid[r][c] = '0'
        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':
                count += 1
                dfs(r, c)

    return count

Complexity Analysis

Metric	DFS	BFS
Time	O(M × N)	O(M × N)
Space (worst case)	O(M × N)	O(min(M, N))

Time: O(M × N)

The outer loop visits every cell exactly once. The DFS or BFS collectively visits each cell at most once more (a cell set to 0 is never revisited). Total work is bounded by 2 × M × N, which simplifies to O(M × N).

Space: DFS vs BFS

DFS space depends on recursion depth. Worst case: all cells are 1 arranged in a single snake-like path. The recursion stack holds one frame per cell, giving O(M × N). For the space complexity implications in other algorithms, see the space complexity guide.

BFS space depends on queue size. The BFS frontier on a grid never exceeds O(min(M, N)) because the wavefront expands layer by layer and is bounded by the shorter grid dimension.

For problems where stack overflow is a concern (grids larger than 500 × 500), BFS or iterative DFS with an explicit stack is safer.

Edge Cases and Variations

Case	Grid	Expected output
Empty grid	[]	0
Single cell, land	[['1']]	1
Single cell, water	[['0']]	0
All water	3 × 3 of 0s	0
All land	3 × 3 of 1s	1

Diagonal Connectivity Variant

Some problems allow 8-directional adjacency (horizontal, vertical, and diagonal). The DFS helper adds four more directions: (r-1, c-1), (r-1, c+1), (r+1, c-1), (r+1, c+1). The time complexity remains O(M × N); only the constant factor per cell increases.

BFS Alternative

Replace the recursive DFS with a queue. Push the starting cell, then repeatedly dequeue a cell, mark it visited, and enqueue its unvisited land neighbours. The island-counting logic in the outer loop stays identical.

Union-Find Alternative

Treat each land cell as a node. Union adjacent land cells. The final count of disjoint sets equals the island count. With path compression and union-by-rank, amortised time is nearly O(M × N). This approach avoids recursion entirely, making it suitable for very large grids.

Connecting the Dots

Grid-based DFS and BFS are the same flood-fill pattern used in image processing, game map generation, and network connectivity analysis. If you have solved the equilibrium index problem using prefix sums, this problem exercises a different muscle: recursive graph traversal on implicit graphs. Both appear in placement rounds at similar frequency.

The O(M × N) traversal you just traced through a 4 × 5 grid scales directly to graph-search problems inside LLM applications: knowledge-graph traversal, retrieval-augmented generation over document graphs, agent planning. TinkerLLM’s guided exercises at ₹299 let you apply DFS and BFS inside an LLM context, turning a placement-prep algorithm into a shipped project.