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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.
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. Other problems with the same pattern: Maximum Number of Points From Grid Queries, Contain Virus, Number of Distinct Islands.

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).