Start practising

Flood Fill

Easy Graphs Matrix Graphs Original on LeetCode

Flood Fill is a easy graphs problem solved with the matrix graphs pattern. The best approach, dfs, runs in O(m · n) time and O(m · n) space. Below are 2 approaches in Java, from bfs up.

Problem

Starting from pixel (sr, sc), recolour it and every pixel connected to it (up, down, left, right) with the same original colour to color. Return the image.

Examples

Example 1

Input
image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output
[[2,2,2],[2,2,0],[2,0,1]]
Why
The bottom-right 1 is not connected to the start.

Example 2

Input
image = [[0,0],[0,0]], sr = 0, sc = 0, color = 0
Output
unchanged

Constraints

  • 1 <= m, n <= 50
  • 4-directional connectivity.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
BFSO(m · n)O(m · n)
DFSO(m · n)O(m · n)

1BFS

TimeO(m · n)
SpaceO(m · n)

Queue the start cell, recolour it, and spread to neighbours that still have the old colour.

  1. If old == color, return the image.
  2. BFS; recolour cells when they are enqueued.
Java
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        if (old == color) return image;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] { sr, sc });
        image[sr][sc] = color;
        while (!q.isEmpty()) {
            int[] c = q.poll();
            for (int[] d : dirs) {
                int r = c[0] + d[0], k = c[1] + d[1];
                if (r >= 0 && k >= 0 && r < image.length && k < image[0].length && image[r][k] == old) {
                    image[r][k] = color;
                    q.add(new int[] { r, k });
                }
            }
        }
        return image;
    }
}

2DFS

TimeO(m · n)
SpaceO(m · n)Recursion depth in the worst case.

Recolour the current cell and recurse into each neighbour that still has the old colour. The new colour works as the visited marker.

  1. If old == color, return.
  2. fill(r, c): bounds and colour check; set colour; recurse 4 ways.
Java
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        if (old != color) fill(image, sr, sc, old, color);
        return image;
    }

    private void fill(int[][] img, int r, int c, int old, int color) {
        if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != old) return;
        img[r][c] = color;
        fill(img, r + 1, c, old, color);
        fill(img, r - 1, c, old, color);
        fill(img, r, c + 1, old, color);
        fill(img, r, c - 1, old, color);
    }
}

Edge cases to test

  • New colour equals the old colour (without a check, the fill loops forever)

Hints

Hint 1

A grid is a graph: each cell is a node and its 4 neighbours are its edges.

FAQ

What is the best time complexity for Flood Fill?

DFS runs in O(m · n) time and O(m · n) extra space.

Which pattern does Flood Fill use?

It is a graphs problem that uses the matrix graphs pattern.

Is there a brute force solution for Flood Fill?

Yes. BFS takes O(m · n) time and O(m · n) space. Queue the start cell, recolour it, and spread to neighbours that still have the old colour.

Which edge cases should I test for Flood Fill?

New colour equals the old colour (without a check, the fill loops forever).