Flood Fill

Problem

Given an image (matrix of colors), a starting pixel (sr, sc), and a new color, paint that pixel and every 4-connected pixel of the original color the new color.

Constraints

• 1 ≤ rows, cols ≤ 50

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def floodFill(self, image, sr, sc, newColor):
        old = image[sr][sc]
        if old == newColor:
            return image
        m, n = len(image), len(image[0])
        def dfs(r, c):
            if 0 <= r < m and 0 <= c < n and image[r][c] == old:
                image[r][c] = newColor
                for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                    dfs(r+dr, c+dc)
        dfs(sr, sc)
        return image

Java

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor == newColor) {
            return image;
        }
        dfs(image, sr, sc, oldColor, newColor);
        return image;
    }

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.