☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Number of islands(Do in Grid and Graph Both)

Medium TUF ID 2833 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an m x n grid of characters where '1' is land and '0' is water. An island is a maximal group of land cells connected horizontally or vertically (not diagonally). Everything outside the grid is water. Return the number of islands.

The sheet asks for two views of the same problem. In the grid view you walk the matrix directly. In the graph view each land cell is a vertex, each pair of side-by-side land cells is an edge, and the answer is the number of connected components of that graph. Solving both makes clear that a grid is just a graph whose edges are implied by positions.

Constraints: 1 ≤ m, n ≤ 300.

Example 1

1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0
answer = 1       // all the land touches through shared sides

Example 2

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
answer = 3       // top-left block, the single centre cell, bottom-right pair

In example 2 the centre cell (2,2) touches (3,3) only at a corner, so they are separate islands.

All three approaches share one idea. Scan every cell. When you find land that has not been seen yet, you have found a new island: count it, then mark every cell of that island as seen so that none of them is counted again. The approaches differ only in how the marking (“flood fill”) is done.

The four neighbours of a cell are reached with these direction arrays:

static final int[] DR = {-1, 1, 0, 0};
static final int[] DC = {0, 0, -1, 1};

Approach 1: Grid DFS (recursive flood fill)

Intuition. From a land cell, recursively visit each of the four neighbours that is in bounds, is land, and has not been seen. The recursion spreads over the whole island and stops at water or the border. Because every cell of the island gets marked, the outer scan will skip them all, and the counter goes up exactly once per island.

A separate seen array is used instead of overwriting '1' with '0', so the caller’s grid is left intact. Overwriting is a common space-saving trick when mutation is allowed.

Algorithm.

  1. For each cell (r, c): if it is land and not seen, increment count and call flood(r, c).
  2. flood(r, c): return if out of bounds, water, or already seen; otherwise mark it and call flood on the four neighbours.
  3. Return count.
static int islandsDfs(char[][] grid) {
    int m = grid.length, n = grid[0].length, count = 0;
    boolean[][] seen = new boolean[m][n];
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1' && !seen[r][c]) {
                count++;                              // first cell of an island we have not met before
                flood(grid, r, c, seen);
            }
        }
    }
    return count;
}

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

Complexity. Time O(m · n): each cell is marked once, and each marked cell makes four constant-time calls. Space O(m · n) for seen plus the recursion depth, which can reach m · n on a snake-shaped island.

That recursion depth is the weakness. A 300 x 300 grid shaped as one long winding path means 90,000 nested calls, which can overflow Java’s default stack.

Approach 2: Grid BFS

Intuition. Do the same flood with a queue. When a new island starts, mark its first cell and enqueue it. Repeatedly dequeue a cell and enqueue each unseen land neighbour. The queue holds only the current “frontier”, and no recursion is involved, so the shape of the island does not matter.

Mark a cell when it is enqueued, not when it is dequeued. Otherwise a cell with two land neighbours already in the queue gets added twice, and on a large blob the queue fills with duplicates.

Algorithm.

  1. For each land cell that is not seen: increment count, mark it, enqueue it.
  2. While the queue is not empty, dequeue a cell and, for each in-bounds neighbour that is land and unseen, mark it and enqueue it.
  3. Return count.
static int islandsBfs(char[][] grid) {
    int m = grid.length, n = grid[0].length, count = 0;
    boolean[][] seen = new boolean[m][n];
    Deque<int[]> queue = new ArrayDeque<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != '1' || seen[r][c]) continue;
            count++;
            seen[r][c] = true;
            queue.add(new int[]{r, c});
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = cell[0] + DR[d], nc = cell[1] + DC[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                    if (grid[nr][nc] == '1' && !seen[nr][nc]) {
                        seen[nr][nc] = true;          // mark when enqueued, not when dequeued
                        queue.add(new int[]{nr, nc});
                    }
                }
            }
        }
    }
    return count;
}

Complexity. Time O(m · n), each cell enqueued at most once. Space O(m · n) for seen; the queue holds at most O(min(m, n)) cells for a typical blob but O(m · n) in the worst case.

Dry run on example 2. Scanning row by row:

scan reaches land and unseen? count cells flooded
(0,0) yes 1 (0,0), (1,0), (0,1), (1,1)
(0,1), (1,0), (1,1) already seen 1  
(2,2) yes 2 (2,2); its neighbours are all water
(3,3) yes 3 (3,3), (3,4)
(3,4) already seen 3  

Approach 3: Graph view, build an adjacency list and count components

Intuition. Turn the grid into an explicit graph. Give every land cell an id 0, 1, 2, ... in row-major order. For each land cell, add an edge to the land cell below it and the land cell to its right, if present. Looking only down and right is enough because every adjacent pair is one cell’s “down” or “right” neighbour, so each edge is added exactly once. Water cells do not become vertices at all.

Now the question is “how many connected components does this graph have?”, which is the classic graph problem: start a traversal from each unvisited vertex and count how many traversals you start. countComponents is the graph solution and works for any undirected adjacency list, not only ones made from grids.

Algorithm.

  1. Assign ids to land cells; let V be the number of land cells.
  2. Build an adjacency list with an edge for each down or right land neighbour.
  3. For each unvisited vertex, increment count and visit its whole component with an explicit stack.
  4. Return count.
static int islandsGraph(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] id = new int[m][n];
    int V = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) id[r][c] = grid[r][c] == '1' ? V++ : -1;
    }
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (id[r][c] < 0) continue;
            if (r + 1 < m && id[r + 1][c] >= 0) addEdge(adj, id[r][c], id[r + 1][c]);   // down
            if (c + 1 < n && id[r][c + 1] >= 0) addEdge(adj, id[r][c], id[r][c + 1]);   // right
        }
    }
    return countComponents(V, adj);
}

static void addEdge(List<List<Integer>> adj, int a, int b) {
    adj.get(a).add(b);
    adj.get(b).add(a);
}

/** The graph form of the problem: number of connected components of an undirected graph. O(V + E) time, O(V) space. */
static int countComponents(int V, List<List<Integer>> adj) {
    boolean[] seen = new boolean[V];
    int count = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (seen[s]) continue;
        count++;
        seen[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int x = stack.pop();
            for (int y : adj.get(x)) {
                if (!seen[y]) {
                    seen[y] = true;
                    stack.push(y);
                }
            }
        }
    }
    return count;
}

Complexity. Time O(m · n): the graph has at most m · n vertices and fewer than 2 · m · n edges, and counting components is linear in their total. Space O(m · n) for the ids and the adjacency list.

This version uses more memory than the grid versions, so it is not what you would submit for the grid problem. Its value is conceptual: it shows that every grid flood fill is a component count on an implicit graph, and the same countComponents answers the graph form of the question (“number of provinces”, “connected components”).

Edge cases and pitfalls