Graph · 8 of 43

Flood fill algo

Use the paint bucket: click one spot and recolor every touching spot that had the same color.

Simple way: time O((m * n)^2)
room O(m * n)
Clever way: time O(m * n)
room O(m * n)

The problem, simply

You get a picture as a grid of numbers with m rows and n columns. Each number is a color. You also get a starting square (sr, sc) and a new color.

Repaint the starting square, and every square connected to it up, down, left or right that has the same old color, with the new color. Return the picture.

A story to remember it

Picture it

grid

Click (1,1). The 1s connected to it form one region. The 1 at the bottom right touches it only at a corner, so it is not part of it.

looking now
checking
path

Examples

The usual picture

In: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Out: [[2,2,2],[2,2,0],[2,0,1]]

Six connected 1s turn into 2. The corner 1 stays.

Same color as before

In: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Out: [[0,0,0],[0,0,0]]

Nothing changes. Code that does not check this first can loop forever.

Corners do not spread

In: image = [[1,0],[0,1]], sr = 0, sc = 0, color = 9
Out: [[9,0],[0,1]]

The two 1s only touch at a corner.

One square

In: image = [[5]], sr = 0, sc = 0, color = 3
Out: [[3]]

Just the clicked square changes.

Way 1: the simple way

Spread the paint one ring at a time by sweeping the whole picture again and again, like letting the juice soak a little more each minute.

Mark the start square as painted.
Sweep every square. If it has the old color, is not painted yet, and touches a painted square, paint it.
Repeat the sweep until a full sweep paints nothing new.

We keep a separate painted grid so we only spread from squares we painted, not from squares that already had the new color.

java

class FloodFillSweeps {
    public static int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int m = image.length, n = image[0].length, old = image[sr][sc];
        boolean[][] painted = new boolean[m][n];
        painted[sr][sc] = true;
        int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean changed = true;
        while (changed) {                                   // one sweep per loop
            changed = false;
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (painted[r][c] || image[r][c] != old) continue;
                    for (int[] s : steps) {
                        int nr = r + s[0], nc = c + s[1];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n && painted[nr][nc]) {
                            painted[r][c] = true;           // touches the wet area
                            changed = true;
                            break;
                        }
                    }
                }
            }
        }
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (painted[r][c]) image[r][c] = color;
        return image;
    }
}

How long it takes: each sweep is O(m * n), and a winding region can need about m * n sweeps, so O((m * n)^2). Extra room: the painted grid, O(m * n).

Way 2: the clever way

Only look where the paint can actually go. Paint a square, then visit its four neighbors right away. Each square is handled once.

Remember the old color. If it equals the new color, return the picture as it is.
fill(r, c): if (r, c) is off the picture or not the old color, stop.
Otherwise paint it, then call fill on up, down, left and right.

Paint a square, then ask its four neighbors

01 / 08

gridpicture

stackcall stack

Click on (1,1). Its color is 1, so every 1 that touches it, and every 1 touching those, turns into 2.

old: 1
new: 2

looking now
checking
done
answer
just added

java

class FloodFillDfs {
    public static int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        if (old == color) return image;                     // nothing to do, and avoids looping forever
        fill(image, sr, sc, old, color);
        return image;
    }

    static void fill(int[][] image, int r, int c, int old, int color) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
        if (image[r][c] != old) return;                     // a wall, or already painted
        image[r][c] = color;
        fill(image, r - 1, c, old, color);   // up
        fill(image, r + 1, c, old, color);   // down
        fill(image, r, c - 1, old, color);   // left
        fill(image, r, c + 1, old, color);   // right
    }

    public static void main(String[] args) {
        int[][] image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        System.out.println(Arrays.deepToString(floodFill(image, 1, 1, 2)));  // [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
    }
}

How long it takes: each square is painted at most once and checked from at most four neighbors, O(m * n). Extra room: the recursion can be as deep as the region is big, O(m * n) in the worst case.

Another way: a waiting line

The same spreading with a queue avoids deep recursion. Paint a square when it joins the line, so it is never added twice.

java

class FloodFillBfs {
    public static int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int old = image[sr][sc];
        if (old == color) return image;
        int m = image.length, n = image[0].length;
        int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Deque<int[]> line = new ArrayDeque<>();
        image[sr][sc] = color;
        line.add(new int[]{sr, sc});
        while (!line.isEmpty()) {
            int[] cell = line.poll();
            for (int[] s : steps) {
                int nr = cell[0] + s[0], nc = cell[1] + s[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == old) {
                    image[nr][nc] = color;                  // paint as it joins the line
                    line.add(new int[]{nr, nc});
                }
            }
        }
        return image;
    }
}

Same O(m * n) time. The line holds at most the edge of the spreading paint, and there is no risk of a stack overflow.

Watch out for

Read the old color before you paint the start square, or you lose it.
Check bounds before reading image[r][c].
Only four directions. Diagonal neighbors are not connected unless the problem says so.
On a huge single-color picture, the recursive way can overflow the call stack. Use the queue version there.

What interviewers ask next

Number of islands is the same spreading, run from every unvisited land square, with a counter.
Surrounded regions: flood fill from every border 'O' first to protect it, then flip the rest.
Color the border of a region only: during the fill, a square is on the border if any neighbor is outside the region or off the grid.
How would a real paint program do it fast? Scanline fill: paint a whole horizontal run at once, then look at the rows above and below for new runs. It uses far fewer calls.

Remember this

Grown-up words: the picture is a grid graph, touching squares are neighbors joined by edges, the spreading region is a connected component, spreading by recursion is depth first search, spreading with a waiting line is breadth first search, and repainting marks squares as visited in place.