10.06Beginner / Intermediate6 topics18 min6 interactive animations

Grid search

Searching a grid as a graph: flood fill, counting islands, connected components, DFS marking, shortest paths with BFS and multi-source BFS. Every cell is a vertex and every allowed move is an edge, so the cost is O(R·C).

Learning goals

Flood fill a region with DFS using a stack or recursion
Count islands and connected components
Find unweighted shortest paths with BFS
Run BFS from several sources

Prerequisites

Neighbourhood reasoningStacks and queues basics

10.06.1

Flood fill

Flood fill recolours the connected region around a start cell, like the paint bucket tool: visit the start, mark it, and spread to every neighbour with the same colour that has not been visited. Mark cells when you push them, not when you pop them, so no cell enters the stack twice. Time and space are O(R·C).

Choose Flood fill and watch the stack of cells waiting to be expanded.

Java

1static int fill(int[][] g, int sr, int sc) {                    // marks land (1) as 2, returns the region size
2    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
3    while (!stack.isEmpty()) {
4        int[] cell = stack.pop(); size++;
5        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
6            int r = cell[0] + d[0], c = cell[1] + d[1];
7            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
8        }
9    }
10    return size;
11}

Flood fill and counting islands (DFS with a stack)

Interactive · edit the input

grid · 3 × 4

0123

Cell being expandedVisited landStart of a new islandWater

Setup

Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.

Step 1 / 10

Java

1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }        // each unvisited land cell starts an island
6    return count;
7}
8static int fill(int[][] g, int sr, int sc) {                      // iterative DFS, marks land as 2
9    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
10    while (!stack.isEmpty()) {
11        int[] cell = stack.pop(); size++;
12        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
13            int r = cell[0] + d[0], c = cell[1] + d[1];
14            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
15        }
16    }
17    return size;
18}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	R=3 C=4	Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.
2	L5	r=0 c=0 islands=1	Unvisited land at (0,0): island number 1 begins.
3	L11	cell=(0,0) islands=1 size=1	Pop (0,0). Unvisited land neighbours pushed: (0,1), (1,0).
4	L11	cell=(1,0) islands=1 size=2	Pop (1,0). No unvisited land neighbours.
5	L11	cell=(0,1) islands=1 size=3	Pop (0,1). No unvisited land neighbours.
6	L5	r=1 c=3 islands=2	Unvisited land at (1,3): island number 2 begins.
7	L11	cell=(1,3) islands=2 size=1	Pop (1,3). Unvisited land neighbours pushed: (2,3).
8	L11	cell=(2,3) islands=2 size=2	Pop (2,3). Unvisited land neighbours pushed: (2,2).
9	L11	cell=(2,2) islands=2 size=3	Pop (2,2). No unvisited land neighbours.
10	L6	return=2	2 islands. Every cell is visited at most once: O(R x C) time, O(R x C) stack in the worst case.

10.06.2

Islands

To count islands (groups of connected land cells), scan the grid and every time you meet an unvisited land cell, increment the count and flood-fill the whole island so its other cells are never counted again. Each cell is processed once by the scan and at most once by a fill: O(R·C).

Run the default grid and read the island count at the end.

Java

1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }
6    return count;
7}

Flood fill and counting islands (DFS with a stack)

Interactive · edit the input

grid · 3 × 4

0123

Cell being expandedVisited landStart of a new islandWater

Setup

Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.

Step 1 / 10

Java

1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }        // each unvisited land cell starts an island
6    return count;
7}
8static int fill(int[][] g, int sr, int sc) {                      // iterative DFS, marks land as 2
9    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
10    while (!stack.isEmpty()) {
11        int[] cell = stack.pop(); size++;
12        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
13            int r = cell[0] + d[0], c = cell[1] + d[1];
14            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
15        }
16    }
17    return size;
18}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	R=3 C=4	Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.
2	L5	r=0 c=0 islands=1	Unvisited land at (0,0): island number 1 begins.
3	L11	cell=(0,0) islands=1 size=1	Pop (0,0). Unvisited land neighbours pushed: (0,1), (1,0).
4	L11	cell=(1,0) islands=1 size=2	Pop (1,0). No unvisited land neighbours.
5	L11	cell=(0,1) islands=1 size=3	Pop (0,1). No unvisited land neighbours.
6	L5	r=1 c=3 islands=2	Unvisited land at (1,3): island number 2 begins.
7	L11	cell=(1,3) islands=2 size=1	Pop (1,3). Unvisited land neighbours pushed: (2,3).
8	L11	cell=(2,3) islands=2 size=2	Pop (2,3). Unvisited land neighbours pushed: (2,2).
9	L11	cell=(2,2) islands=2 size=3	Pop (2,2). No unvisited land neighbours.
10	L6	return=2	2 islands. Every cell is visited at most once: O(R x C) time, O(R x C) stack in the worst case.

10.06.3

Connected components

Islands are connected components of the grid graph. The same pattern counts components in any graph: loop over the vertices, start a search from each unvisited one, and count the starts. Union-find is the alternative when connections arrive over time, for example when land cells are added one by one.

Adjacency matters: with diagonal moves allowed, two land cells touching only at a corner would join into one component, while 4-direction adjacency keeps them separate.

Java

1static int[] labelComponents(int[][] g) {                  // returns {component count, largest size}
2    int comps = 0, largest = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { comps++; largest = Math.max(largest, fill(g, r, c)); }
6    return new int[]{comps, largest};
7}

Flood fill and counting islands (DFS with a stack)

Interactive · edit the input

grid · 3 × 4

0123

Cell being expandedVisited landStart of a new islandWater

Setup

Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.

Step 1 / 10

Java

1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }        // each unvisited land cell starts an island
6    return count;
7}
8static int fill(int[][] g, int sr, int sc) {                      // iterative DFS, marks land as 2
9    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
10    while (!stack.isEmpty()) {
11        int[] cell = stack.pop(); size++;
12        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
13            int r = cell[0] + d[0], c = cell[1] + d[1];
14            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
15        }
16    }
17    return size;
18}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	R=3 C=4	Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.
2	L5	r=0 c=0 islands=1	Unvisited land at (0,0): island number 1 begins.
3	L11	cell=(0,0) islands=1 size=1	Pop (0,0). Unvisited land neighbours pushed: (0,1), (1,0).
4	L11	cell=(1,0) islands=1 size=2	Pop (1,0). No unvisited land neighbours.
5	L11	cell=(0,1) islands=1 size=3	Pop (0,1). No unvisited land neighbours.
6	L5	r=1 c=3 islands=2	Unvisited land at (1,3): island number 2 begins.
7	L11	cell=(1,3) islands=2 size=1	Pop (1,3). Unvisited land neighbours pushed: (2,3).
8	L11	cell=(2,3) islands=2 size=2	Pop (2,3). Unvisited land neighbours pushed: (2,2).
9	L11	cell=(2,2) islands=2 size=3	Pop (2,2). No unvisited land neighbours.
10	L6	return=2	2 islands. Every cell is visited at most once: O(R x C) time, O(R x C) stack in the worst case.

10.06.4

Shortest path in unweighted grid

Breadth-first search explores cells in order of distance: all cells at distance 0, then 1, then 2. Because every move costs 1, the first time BFS reaches a cell is its shortest distance. Keep a queue and a dist array initialised to -1 (unreached). O(R·C) time. Depth-first search does not give shortest paths.

Run the default grid: the walls force a detour.

Java

1static int shortestPath(int[][] g) {                          // 0 = wall; from (0, 0) to (R - 1, C - 1)
2    int R = g.length, C = g[0].length;
3    if (g[0][0] == 0) return -1;
4    int[][] dist = new int[R][C]; for (int[] row : dist) Arrays.fill(row, -1);
5    Deque<int[]> queue = new ArrayDeque<>(); dist[0][0] = 0; queue.offer(new int[]{0, 0});
6    while (!queue.isEmpty()) {
7        int[] cur = queue.poll();
8        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
9            int r = cur[0] + d[0], c = cur[1] + d[1];
10            if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0 || dist[r][c] != -1) continue;
11            dist[r][c] = dist[cur[0]][cur[1]] + 1;
12            queue.offer(new int[]{r, c});
13        }
14    }
15    return dist[R - 1][C - 1];
16}

BFS on a grid: shortest path and multi-source distances

Interactive · edit the input

grid · 3 × 5

01234

▇

Cell being expandedReached (distance shown)WallSource

queue (front first)

(0,0)

Setup

Start at the top-left cell with distance 0.

Step 1 / 14

Java

1static int shortestPath(int[][] g) {                     // 4-directional moves, 0 = wall
2    int R = g.length, C = g[0].length;
3    int[][] dist = new int[R][C]; for (int[] row : dist) Arrays.fill(row, -1);
4    Deque<int[]> queue = new ArrayDeque<>();
5    // single source: (0, 0); multi-source: every cell equal to 2, all at distance 0
6    dist[0][0] = 0; queue.offer(new int[]{0, 0});
7    while (!queue.isEmpty()) {
8        int[] cur = queue.poll();
9        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
10            int r = cur[0] + d[0], c = cur[1] + d[1];
11            if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0 || dist[r][c] != -1) continue;
12            dist[r][c] = dist[cur[0]][cur[1]] + 1;           // first arrival is the shortest, because BFS goes level by level
13            queue.offer(new int[]{r, c});
14        }
15    }
16    return dist[R - 1][C - 1];                               // -1 when unreachable; multi-source: max over all cells
17}

Live state

sources

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L5	sources=1	Start at the top-left cell with distance 0.
2	L12	cell=(0,0) dist=0	Expand (0,0) at distance 0: reached (0,1)=1.
3	L12	cell=(0,1) dist=1	Expand (0,1) at distance 1: reached (1,1)=2.
4	L12	cell=(1,1) dist=2	Expand (1,1) at distance 2: reached (1,2)=3, (2,1)=3.
5	L12	cell=(1,2) dist=3	Expand (1,2) at distance 3: reached (1,3)=4, (2,2)=4.
6	L12	cell=(2,1) dist=3	Expand (2,1): every open neighbour is already reached or blocked.
7	L12	cell=(1,3) dist=4	Expand (1,3) at distance 4: reached (0,3)=5, (1,4)=5, (2,3)=5.
8	L12	cell=(2,2) dist=4	Expand (2,2): every open neighbour is already reached or blocked.
9	L12	cell=(0,3) dist=5	Expand (0,3) at distance 5: reached (0,4)=6.
10	L12	cell=(1,4) dist=5	Expand (1,4) at distance 5: reached (2,4)=6.
11	L12	cell=(2,3) dist=5	Expand (2,3): every open neighbour is already reached or blocked.
12	L12	cell=(0,4) dist=6	Expand (0,4): every open neighbour is already reached or blocked.
13	L12	cell=(2,4) dist=6	Expand (2,4): every open neighbour is already reached or blocked.
14	L16	return=6	The bottom-right cell is 6 steps away, the minimum, because BFS reaches cells in order of distance.

10.06.5

Multi-source BFS

Multi-source BFS starts with every source in the queue at distance 0, so each cell ends up with the distance to its nearest source. It is the standard solution for rotting oranges (time until everything rots) and “distance to the nearest 0”. Still O(R·C): each cell is queued once.

Switch the animation to the multi-source task and try the unreachable preset.

Java

1for (int r = 0; r < R; r++)
2    for (int c = 0; c < C; c++)
3        if (g[r][c] == 2) { dist[r][c] = 0; queue.offer(new int[]{r, c}); }   // all sources first
4// then run the same BFS loop; the answer is the largest dist, or -1 if an open cell stays at -1

BFS on a grid: shortest path and multi-source distances

Interactive · edit the input

grid · 3 × 5

01234

▇

Cell being expandedReached (distance shown)WallSource

queue (front first)

(0,0)

Setup

Start at the top-left cell with distance 0.

Step 1 / 14

Java

1static int shortestPath(int[][] g) {                     // 4-directional moves, 0 = wall
2    int R = g.length, C = g[0].length;
3    int[][] dist = new int[R][C]; for (int[] row : dist) Arrays.fill(row, -1);
4    Deque<int[]> queue = new ArrayDeque<>();
5    // single source: (0, 0); multi-source: every cell equal to 2, all at distance 0
6    dist[0][0] = 0; queue.offer(new int[]{0, 0});
7    while (!queue.isEmpty()) {
8        int[] cur = queue.poll();
9        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
10            int r = cur[0] + d[0], c = cur[1] + d[1];
11            if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0 || dist[r][c] != -1) continue;
12            dist[r][c] = dist[cur[0]][cur[1]] + 1;           // first arrival is the shortest, because BFS goes level by level
13            queue.offer(new int[]{r, c});
14        }
15    }
16    return dist[R - 1][C - 1];                               // -1 when unreachable; multi-source: max over all cells
17}

Live state

sources

No condition evaluated on this step

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L5	sources=1	Start at the top-left cell with distance 0.
2	L12	cell=(0,0) dist=0	Expand (0,0) at distance 0: reached (0,1)=1.
3	L12	cell=(0,1) dist=1	Expand (0,1) at distance 1: reached (1,1)=2.
4	L12	cell=(1,1) dist=2	Expand (1,1) at distance 2: reached (1,2)=3, (2,1)=3.
5	L12	cell=(1,2) dist=3	Expand (1,2) at distance 3: reached (1,3)=4, (2,2)=4.
6	L12	cell=(2,1) dist=3	Expand (2,1): every open neighbour is already reached or blocked.
7	L12	cell=(1,3) dist=4	Expand (1,3) at distance 4: reached (0,3)=5, (1,4)=5, (2,3)=5.
8	L12	cell=(2,2) dist=4	Expand (2,2): every open neighbour is already reached or blocked.
9	L12	cell=(0,3) dist=5	Expand (0,3) at distance 5: reached (0,4)=6.
10	L12	cell=(1,4) dist=5	Expand (1,4) at distance 5: reached (2,4)=6.
11	L12	cell=(2,3) dist=5	Expand (2,3): every open neighbour is already reached or blocked.
12	L12	cell=(0,4) dist=6	Expand (0,4): every open neighbour is already reached or blocked.
13	L12	cell=(2,4) dist=6	Expand (2,4): every open neighbour is already reached or blocked.
14	L16	return=6	The bottom-right cell is 6 steps away, the minimum, because BFS reaches cells in order of distance.

10.06.6

DFS marking

DFS marking visits a cell, marks it, and recursively marks its neighbours. Recursion is short but can overflow the Java call stack on large grids (depth up to R·C), so for big inputs use an explicit stack or BFS. Mark by overwriting the grid (a value such as 2) or with a separate boolean[][] visited if the input must stay unchanged.

Compare the stack in the animation with the recursion you would write.

Java

1static void dfs(int[][] g, int r, int c) {                    // recursive, fine for small grids
2    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != 1) return;
3    g[r][c] = 2;                                              // mark before recursing
4    dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r + 1, c); dfs(g, r, c - 1);
5}

Flood fill and counting islands (DFS with a stack)

Interactive · edit the input

grid · 3 × 4

0123

Cell being expandedVisited landStart of a new islandWater

Setup

Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.

Step 1 / 10

Java

1static int countIslands(int[][] g) {
2    int count = 0;
3    for (int r = 0; r < g.length; r++)
4        for (int c = 0; c < g[0].length; c++)
5            if (g[r][c] == 1) { count++; fill(g, r, c); }        // each unvisited land cell starts an island
6    return count;
7}
8static int fill(int[][] g, int sr, int sc) {                      // iterative DFS, marks land as 2
9    Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{sr, sc}); g[sr][sc] = 2; int size = 0;
10    while (!stack.isEmpty()) {
11        int[] cell = stack.pop(); size++;
12        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
13            int r = cell[0] + d[0], c = cell[1] + d[1];
14            if (r >= 0 && r < g.length && c >= 0 && c < g[0].length && g[r][c] == 1) { g[r][c] = 2; stack.push(new int[]{r, c}); }
15        }
16    }
17    return size;
18}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	R=3 C=4	Scan every cell; each unvisited land cell starts a new island, and a DFS marks the whole island so it is never counted twice.
2	L5	r=0 c=0 islands=1	Unvisited land at (0,0): island number 1 begins.
3	L11	cell=(0,0) islands=1 size=1	Pop (0,0). Unvisited land neighbours pushed: (0,1), (1,0).
4	L11	cell=(1,0) islands=1 size=2	Pop (1,0). No unvisited land neighbours.
5	L11	cell=(0,1) islands=1 size=3	Pop (0,1). No unvisited land neighbours.
6	L5	r=1 c=3 islands=2	Unvisited land at (1,3): island number 2 begins.
7	L11	cell=(1,3) islands=2 size=1	Pop (1,3). Unvisited land neighbours pushed: (2,3).
8	L11	cell=(2,3) islands=2 size=2	Pop (2,3). Unvisited land neighbours pushed: (2,2).
9	L11	cell=(2,2) islands=2 size=3	Pop (2,2). No unvisited land neighbours.
10	L6	return=2	2 islands. Every cell is visited at most once: O(R x C) time, O(R x C) stack in the worst case.

Practice ladder

Now try it yourself

Easy

Count the islands of [[1, 1, 0], [0, 0, 1], [1, 0, 1]]
Flood fill the region containing the top-left land cell

Medium

Find the size of the largest island
Compute the shortest path in a maze with BFS

Advanced

Rotting oranges: how many minutes until every orange is rotten, or -1?

Key takeaways

Grid search is graph search: cells are vertices, moves are edges, cost O(R·C).
DFS marks regions; BFS gives shortest paths in unweighted grids.
Seed every source at distance 0 for multi-source BFS; use an explicit stack for huge grids.