☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Flood-fill Algorithm

Medium TUF ID 2832 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

An image is an m × n grid of integers, each integer being a pixel’s colour. Given a starting pixel (sr, sc) and a new colour color, perform a flood fill: recolour the starting pixel, and every pixel connected to it 4-directionally (up, down, left, right) through pixels of the starting pixel’s original colour, to color. Return the resulting image. This is the paint-bucket tool in any drawing program.

Diagonal neighbours do not count as connected. The methods here return a new image and leave the input unchanged; LeetCode also accepts modifying the input in place.

Constraints (LeetCode): 1 ≤ m, n ≤ 50, 0 ≤ image[i][j], color < 2^16, and (sr, sc) is inside the grid.

Example 1

image = [[1,1,1],        sr = 1, sc = 1, color = 2
         [1,1,0],
         [1,0,1]]
result = [[2,2,2],
          [2,2,0],
          [2,0,1]]

The region of 1s containing the centre is recoloured. The bottom-right 1 touches the region only diagonally, so it stays 1.

Example 2

image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
result = [[0,0,0],[0,0,0]]   // the region already has the new colour

Approach 1: Brute force, grow the region by repeated sweeps

Intuition. The region can be described by a local rule: the starting pixel is in it, and a pixel joins it if it has the original colour and one of its four neighbours is already in it. Apply that rule to every pixel of the grid, again and again, until a full sweep adds nothing. At that point the rule cannot grow the region any further, which means we have found every pixel reachable from the start.

Membership has to be tracked in a separate boolean grid. Checking “does a neighbour already have the new colour?” would be wrong, because the new colour may already appear elsewhere in the image, outside the region.

The problem is speed. One sweep scans the whole grid, and a single sweep may add very few pixels. Picture a winding corridor whose path runs against the sweep direction: each sweep extends it by roughly one pixel.

Algorithm.

  1. Copy the image. Mark inRegion[sr][sc] = true.
  2. Repeat until a sweep makes no change: for every pixel not yet in the region that has the original colour, add it if any in-grid neighbour is in the region.
  3. Paint every pixel marked in the region with color.
static int[][] bruteForce(int[][] image, int sr, int sc, int color) {
    int[][] img = copy(image);
    int m = img.length, n = img[0].length, original = img[sr][sc];
    boolean[][] inRegion = new boolean[m][n];
    inRegion[sr][sc] = true;
    boolean changed = true;
    while (changed) {                                       // each sweep adds at least one cell or stops
        changed = false;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (inRegion[r][c] || img[r][c] != original) continue;
                for (int d = 0; d < 4; d++) {
                    int nr = r + DR[d], nc = c + DC[d];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && inRegion[nr][nc]) {
                        inRegion[r][c] = true;
                        changed = true;
                        break;
                    }
                }
            }
        }
    }
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (inRegion[r][c]) img[r][c] = color;
    return img;
}

Complexity. Time O((m·n)^2) in the worst case: up to m·n sweeps, each costing O(m·n). Space O(m·n) for the membership grid and the copy.

Approach 2: Recursive DFS

Intuition. Look at the grid as a graph: each pixel is a vertex, and two adjacent pixels are joined by an edge when both have the original colour. The region we must paint is then simply the connected component that contains the start pixel, and depth-first search visits exactly one connected component.

There is a neat trick that removes the need for a separate visited array: the new colour itself is the visited mark. Once a pixel has been painted, it no longer equals the original colour, so the recursion never enters it again.

That trick has one trap. If color equals the original colour, painting changes nothing, every pixel still looks unvisited, and the recursion bounces between two neighbours forever until it throws StackOverflowError. The fix is to return immediately in that case, which is also the correct answer since the image would not change.

Algorithm.

  1. Copy the image and read original = img[sr][sc]. If it equals color, return the copy.
  2. paint(r, c): if (r, c) is outside the grid or does not have the original colour, return.
  3. Otherwise set it to color and call paint on its four neighbours.
static int[][] dfs(int[][] image, int sr, int sc, int color) {
    int[][] img = copy(image);
    int original = img[sr][sc];
    if (original != color) paint(img, sr, sc, original, color);   // same colour: nothing to do, and no infinite loop
    return img;
}

static void paint(int[][] img, int r, int c, int original, int color) {
    if (r < 0 || r >= img.length || c < 0 || c >= img[0].length || img[r][c] != original) return;
    img[r][c] = color;                                      // recolouring doubles as the "visited" mark
    for (int d = 0; d < 4; d++) paint(img, r + DR[d], c + DC[d], original, color);
}

Complexity. Time O(m·n): every pixel is painted at most once and examined from at most four neighbours. Space O(m·n) in the worst case for the recursion depth (a region shaped like one long corridor), plus the copy. For LeetCode’s 50 × 50 limit that is at most 2,500 frames, which is fine.

Approach 3: Iterative BFS

Intuition. Breadth-first search finds the same connected component, layer by layer outward from the start, using a queue instead of the call stack. The result is identical; the advantage is robustness. On a large image (for example 2000 × 2000), a corridor-shaped region would need millions of nested recursive calls, far beyond Java’s default stack, while a queue simply lives on the heap.

Paint each pixel when it is enqueued, not when it is dequeued. If painting waited until dequeue, a pixel that is still waiting in the queue would still look unvisited, and up to four different neighbours could enqueue it.

Algorithm.

  1. Copy the image. If the original colour equals color, return the copy.
  2. Paint the start pixel and enqueue it.
  3. While the queue is not empty: dequeue a pixel; for each of its four neighbours that is inside the grid and still has the original colour, paint it and enqueue it.
static int[][] bfs(int[][] image, int sr, int sc, int color) {
    int[][] img = copy(image);
    int original = img[sr][sc];
    if (original == color) return img;
    int m = img.length, n = img[0].length;
    ArrayDeque<int[]> queue = new ArrayDeque<>();
    img[sr][sc] = color;                                    // colour when enqueued, so no cell enters twice
    queue.offer(new int[]{sr, sc});
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int d = 0; d < 4; d++) {
            int r = cell[0] + DR[d], c = cell[1] + DC[d];
            if (r >= 0 && r < m && c >= 0 && c < n && img[r][c] == original) {
                img[r][c] = color;
                queue.offer(new int[]{r, c});
            }
        }
    }
    return img;
}

The direction arrays DR and DC list up, down, left and right; both traversal methods share them.

Dry run on Example 1, start (1,1), original colour 1, new colour 2:

step dequeued painted and enqueued queue after
0   (1,1) (1,1)
1 (1,1) (0,1), (1,0); below and right are 0 (0,1), (1,0)
2 (0,1) (0,0), (0,2) (1,0), (0,0), (0,2)
3 (1,0) (2,0) (0,0), (0,2), (2,0)
4-6 (0,0), (0,2), (2,0) none empty

Pixel (2,2) is never reached, because both of its neighbours, (1,2) and (2,1), are 0.

Complexity. Time O(m·n), as for DFS. Space O(m·n) in the worst case for the queue, plus the copy.

Edge cases and pitfalls