Flood Fill

Easy Problem 98 of 151 Java and Python

Problem

An image is an m × n grid of integers. Given a starting pixel (sr, sc) and a color, perform a flood fill: recolour the starting pixel and every pixel connected to it (up, down, left, right) that has the same original colour, and so on outwards.

Return the modified image.

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, 0, 0]], sr = 0, sc = 0, color = 0
Output: [[0, 0, 0], [0, 0, 0]]
Why: Already that colour: nothing changes.

Constraints

1 ≤ m, n ≤ 50
0 ≤ image[i][j], color < 2¹⁶

Explanation

A grid is a graph: each cell is a node connected to its four neighbours. Flood fill is "visit every node reachable from the start through same-coloured cells", which is exactly what DFS or BFS does.

Recolouring a cell also marks it as visited. The one trap: if the new colour equals the old one, nothing would ever look visited, so return early.

Approach 1 · Better

BFS with a queue

Time O(m · n)
Space O(m · n) queue

Start a queue at the starting pixel, recolour cells as they are added, and add their same-coloured neighbours.

If image[sr][sc] already equals color, return.
Recolour the start and add it to a queue.
Pop a cell; for each neighbour with the original colour, recolour it and enqueue it.

Java

import java.util.*;

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 } };
        Deque<int[]> queue = new ArrayDeque<>();
        image[sr][sc] = color;
        queue.add(new int[] { sr, sc });
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r >= 0 && c >= 0 && r < image.length && c < image[0].length && image[r][c] == old) {
                    image[r][c] = color;
                    queue.add(new int[] { r, c });
                }
            }
        }
        return image;
    }
}

Python

from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        old = image[sr][sc]
        if old == color:
            return image
        m, n = len(image), len(image[0])
        image[sr][sc] = color
        queue = deque([(sr, sc)])
        while queue:
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == old:
                    image[nr][nc] = color
                    queue.append((nr, nc))
        return image

Approach 2 · Optimal

Recursive DFS

Time O(m · n)
Space O(m · n) recursion in the worst case

Recolour the cell and recurse into each neighbour that still has the original colour.

If the colour is unchanged, return the image.
fill(r, c): stop if out of bounds or not the original colour; otherwise recolour and recurse four ways.

Java

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] != color) {
            fill(image, sr, sc, image[sr][sc], color);
        }
        return image;
    }

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

Python

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        old = image[sr][sc]
        m, n = len(image), len(image[0])

        def fill(r, c):
            if not (0 <= r < m and 0 <= c < n) or image[r][c] != old:
                return
            image[r][c] = color
            fill(r + 1, c)
            fill(r - 1, c)
            fill(r, c + 1)
            fill(r, c - 1)

        if old != color:
            fill(sr, sc)
        return image

Complexity compared

Approach	Time	Space
Better BFS with a queue	O(m · n)	O(m · n) queue
Optimal Recursive DFS	O(m · n)	O(m · n) recursion in the worst case

Key takeaways

Grid problems are graph problems; four-direction neighbours are the edges.
Recursive DFS can overflow the stack on large grids; BFS cannot.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem