☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Flood fill algorithm

Medium TUF ID 531 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

An image is an n x m grid of integers, each one a pixel colour. Given a starting pixel (sr, sc) and a new colour, perform a flood fill: repaint the starting pixel, and every pixel connected to it through up, down, left or right neighbours of the same original colour, with the new colour. Return the resulting image. This is the paint-bucket tool of every drawing program.

Constraints: 1 ≤ n, m ≤ 50, 0 ≤ colours < 2^16. The methods below return a new image and leave the input untouched, so the tests can run all three on the same grid.

Example 1

image = 1 1 1        sr = 1, sc = 1, color = 2
        1 1 0
        1 0 1
answer = 2 2 2
         2 2 0
         2 0 1      // the bottom-right 1 touches the region only diagonally, so it stays 1

Example 2

image = 0 0 0        sr = 0, sc = 0, color = 0
        0 0 0
answer = unchanged  // the new colour equals the old one

The region to repaint is a connected component of an implicit graph: pixels are vertices, and two side-adjacent pixels with the start’s original colour are joined by an edge. Finding it is a single traversal from (sr, sc).

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

Intuition. Keep a boolean grid inRegion, initially containing only the start. Sweep the whole image: any pixel with the original colour that touches a pixel already in the region joins it. A single sweep is not enough, because the region can only spread “backwards” (up and left) one step per sweep, so repeat sweeps until one adds nothing. Then paint every pixel of the region.

Using a separate inRegion grid instead of painting as we go matters when the new colour already appears in the image. In [[1, 2], [1, 1]] filled from (0, 0) with colour 2, the original 2 at (0, 1) is not part of the region; it just happens to share the new colour.

Algorithm.

  1. original = image[sr][sc]; inRegion[sr][sc] = true.
  2. Repeat full sweeps: a pixel not yet in the region, with colour original, and with a side neighbour in the region, joins the region. Stop when a sweep adds nothing.
  3. Copy the image and paint every region pixel with color.
static final int[][] DIRS = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

static int[][] bruteForce(int[][] image, int sr, int sc, int color) {
    int n = image.length, m = image[0].length;
    int original = image[sr][sc];
    boolean[][] inRegion = new boolean[n][m];
    inRegion[sr][sc] = true;
    boolean grew = true;
    while (grew) {
        grew = false;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (inRegion[r][c] || image[r][c] != original) continue;
                for (int[] d : DIRS) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && inRegion[nr][nc]) {
                        inRegion[r][c] = true;        // same colour and touching the region: it belongs
                        grew = true;
                        break;
                    }
                }
            }
        }
    }
    int[][] result = copy(image);
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) if (inRegion[r][c]) result[r][c] = color;
    }
    return result;
}

Complexity. Time O((n * m)^2): each sweep costs O(n * m), and a winding region can need up to O(n * m) sweeps, since the region may grow by just one pixel per sweep. Space O(n * m) for inRegion and the copy. It is correct, and even sidesteps the “same colour” trap below without special handling, but it wastes time re-examining pixels far from the growing edge.

Approach 2: DFS

Intuition. Start at (sr, sc) and spread directly. Paint the current pixel, then recurse into its four neighbours; any neighbour that is out of bounds or does not have the original colour stops the recursion. Repainting a pixel is also its “visited” mark: once it has the new colour it no longer matches original, so it is never entered again.

That trick has one hole. If color == original, painting changes nothing, every pixel keeps matching, and the recursion bounces between neighbours forever (in practice, until StackOverflowError). The fix is a guard: when the colours are equal, the answer is the unchanged image, so return immediately.

Algorithm.

  1. Copy the image; original = img[sr][sc].
  2. If original == color, return the copy.
  3. paint(r, c): return if out of bounds or img[r][c] != original. Otherwise set img[r][c] = color and call paint on the 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);   // equal colours: nothing to do, and no way to tell visited cells apart
    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;
    paint(img, r + 1, c, original, color);
    paint(img, r - 1, c, original, color);
    paint(img, r, c + 1, original, color);
    paint(img, r, c - 1, original, color);
}

Dry run on example 1, original = 1, starting at (1,1):

call pixel colour action
paint(1,1) 1 paint; go down
paint(2,1) 0 stop
paint(0,1) 1 paint; its down neighbour (1,1) is already 2, stop; go on to (0,2) and (0,0)
paint(0,2) 1 paint; down (1,2) is 0, stop
paint(0,0) 1 paint; down (1,0) is 1
paint(1,0) 1 paint; down (2,0) is 1
paint(2,0) 1 paint; all neighbours stop

The pixel (2,2) is never reached: its only side neighbours are (1,2) and (2,1), both 0.

Complexity. Time O(n * m): each pixel is painted at most once and each paint makes four constant-time calls. Space O(n * m) for the copy plus the recursion depth, which can reach n * m for a snake-shaped region. With 50 x 50 = 2500 that is safe; for large images prefer BFS.

Approach 3: BFS

Intuition. The same spread with an explicit queue instead of recursion. Paint the start and enqueue it; repeatedly poll a pixel and, for each side neighbour that still has the original colour, paint it and enqueue it. Painting at enqueue time is again the visited mark, so no pixel is queued twice. The order of painting differs from DFS (rings around the start instead of long arms), but the final image is identical, since both paint exactly the connected region.

Algorithm.

  1. Copy the image; if original == color, return the copy.
  2. Paint the start and enqueue it.
  3. While the queue is non-empty: poll a pixel; for each in-bounds neighbour with colour original, 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 n = img.length, m = img[0].length;
    Deque<int[]> queue = new ArrayDeque<>();
    img[sr][sc] = color;
    queue.add(new int[]{sr, sc});
    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 || img[nr][nc] != original) continue;
            img[nr][nc] = color;                      // paint on enqueue so the cell is never queued twice
            queue.add(new int[]{nr, nc});
        }
    }
    return img;
}

static int[][] copy(int[][] image) {
    int[][] out = new int[image.length][];
    for (int i = 0; i < image.length; i++) out[i] = image[i].clone();
    return out;
}

Complexity. Time O(n * m), space O(n * m) for the copy and the queue, with no recursion depth limit.

Edge cases and pitfalls