Topics › Graphs › Problems on BFS/DFS

Connected Components Problem in Matrix

Medium TUF ID 2830 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an n x m grid of characters, '1' for land and '0' for water. Two land cells belong to the same island if they touch horizontally, vertically or diagonally, that is, if one is among the other’s 8 surrounding cells. Return the number of islands.

This is the A2Z sheet’s “number of islands” lecture, the GeeksforGeeks version with 8-directional connectivity. The LeetCode version (problem 200) counts only the 4 side neighbours. The two differ in a single line, the list of directions, so every method here takes a diagonals flag and the tests check both answers.

Constraints: 1 ≤ n, m ≤ 500.

Example 1

grid = 0 1 1 1 0 0 0
       0 0 1 1 0 1 0
answer = 2          // the blob at columns 1-3, and the lone cell at (1, 5)

Example 2

grid = 0 1
       1 0
       1 1
       1 0
answer = 1          // (0,1) touches (1,0) at a corner; with 4 directions the answer would be 2

The grid is a graph in disguise. Every land cell is a vertex, and an edge joins each pair of neighbouring land cells. No adjacency list is ever built; the neighbours of a cell are computed on the fly from a direction table. Counting islands is then counting the connected components of that implicit graph.

static final int[][] DIRS4 = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
static final int[][] DIRS8 = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} };

Approach 1: BFS flood from each unvisited land cell

Intuition. Scan the grid row by row. When you meet a land cell that no earlier flood has reached, it is the first cell of a new island: count it, then flood the entire island with a BFS so that none of its other cells are counted again. A flood visits every land cell reachable from the start through land neighbours, which is exactly one island. When the scan finishes, every island has been counted once, at its first cell in reading order.

Algorithm.

1. visited all false, islands = 0.
2. For each cell (r, c): if it is '1' and unvisited, increment islands, mark it and enqueue it.
3. While the queue is non-empty: poll a cell; for each of the 4 or 8 directions, if the neighbour is inside the grid, is land and is unvisited, mark it and enqueue it.

static int bfs(char[][] grid, boolean diagonals) {
    if (grid.length == 0) return 0;
    int n = grid.length, m = grid[0].length;
    int[][] dirs = diagonals ? DIRS8 : DIRS4;
    boolean[][] visited = new boolean[n][m];
    Deque<int[]> queue = new ArrayDeque<>();
    int islands = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] != '1' || visited[r][c]) continue;
            islands++;                                    // a land cell no earlier flood reached
            visited[r][c] = true;
            queue.add(new int[]{r, c});
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if (grid[nr][nc] == '1' && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        queue.add(new int[]{nr, nc});
                    }
                }
            }
        }
    }
    return islands;
}

Dry run on example 2 with diagonals:

With 4 directions, the flood from (0,1) finds no land neighbour ((0,0) and (1,1) are water), so it stops at one cell. The scan then reaches (1,0), which is unvisited, and starts a second island. The answer is 2.

Complexity. Time O(n * m): each cell is scanned once by the outer loop, enqueued at most once, and checks at most 8 neighbours. Space O(n * m) for visited, plus the queue, which in the worst case holds a whole frontier of the grid.

Approach 2: DFS flood

Intuition. The flood can just as well be a depth-first search: mark the cell, then recurse into each of its neighbours. Out-of-grid, water and already-visited cells simply return. The counting loop is identical; only the flood changes. The recursive version is shorter to write, which is why it is the most common solution in interviews.

Algorithm.

1. Same outer loop as approach 1.
2. flood(r, c): return if (r, c) is outside the grid, is water, or is visited. Otherwise mark it and call flood on every neighbour.

static int dfs(char[][] grid, boolean diagonals) {
    if (grid.length == 0) return 0;
    int n = grid.length, m = grid[0].length;
    boolean[][] visited = new boolean[n][m];
    int islands = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] == '1' && !visited[r][c]) {
                islands++;
                flood(grid, r, c, visited, diagonals ? DIRS8 : DIRS4);
            }
        }
    }
    return islands;
}

static void flood(char[][] grid, int r, int c, boolean[][] visited, int[][] dirs) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
    if (grid[r][c] != '1' || visited[r][c]) return;
    visited[r][c] = true;
    for (int[] d : dirs) flood(grid, r + d[0], c + d[1], visited, dirs);
}

Complexity. Time O(n * m), space O(n * m). The catch is the recursion depth: a snake-shaped island can make the DFS go n * m calls deep, and 500 x 500 = 250000 frames will overflow Java’s default stack. For large grids use BFS, an explicit stack, or run the code in a thread with a bigger stack. The tests keep DFS on a 40 x 40 all-land grid, which is at most 1600 frames.

A common space saving is to “sink” each visited cell by overwriting '1' with '0' instead of keeping a visited array. That works, but it destroys the caller’s grid. The methods here leave the input untouched so that all three can be run on the same grid.

Approach 3: Union-find over cells

Intuition. Number each cell r * m + c so that cells can live in a union-find structure. Count every land cell as an island of its own, then, for every pair of neighbouring land cells, union them; each successful union merges two islands into one and decrements the count. What is left is the number of components. Every pair of neighbours is examined twice (once from each side), but the second attempt finds both cells already in one set and changes nothing.

Algorithm.

1. parent[i] = i for every cell, islands = 0.
2. For each land cell: increment islands; for each land neighbour, find both roots and, if they differ, link them and decrement islands.
3. Return islands.

static int unionFind(char[][] grid, boolean diagonals) {
    if (grid.length == 0) return 0;
    int n = grid.length, m = grid[0].length;
    int[][] dirs = diagonals ? DIRS8 : DIRS4;
    int[] parent = new int[n * m];
    for (int i = 0; i < n * m; i++) parent[i] = i;
    int islands = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (grid[r][c] != '1') continue;
            islands++;                                    // a new island of one cell, until merged
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= m || grid[nr][nc] != '1') continue;
                int a = find(parent, r * m + c), b = find(parent, nr * m + nc);
                if (a != b) {
                    parent[a] = b;
                    islands--;
                }
            }
        }
    }
    return islands;
}

static int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

Complexity. Time O(n * m * α(n * m)), space O(n * m) for parent. No recursion and no queue. Union-find is the right tool when land appears cell by cell and the island count is needed after each addition, which is exactly the “Number of islands II” problem.

Edge cases and pitfalls

• 4 versus 8 directions. Read the statement carefully. The checkerboard 101 / 010 / 101 is one island with diagonals and five without.
• Characters, not integers. The grid holds '1' and '0'. Comparing with 1 (the integer) compiles in Java, because char is numeric, but is always false.
• Bounds checks before access. Test nr and nc against the grid size before reading grid[nr][nc].
• Mark when enqueueing. In BFS, mark a cell visited as soon as it is pushed; marking on poll lets the same cell be queued several times.
• Empty and degenerate grids. No rows, all water (answer 0), a single cell, a single row or column. The methods guard against grid.length == 0 before reading grid[0].
• Recursion depth in the DFS flood, discussed above.

Related problems

• Number of islands(Do in Grid and Graph Both) is the 4-directional LeetCode version.
• Connected Components counts components when the graph is an explicit edge list.
• Flood fill algorithm is one flood from a given cell.
• Number of enclaves and Surrounded Regions flood from the border instead.
• Number of islands II is the online, union-find version.