Flood Fill

Problem statement

You get a 2D image of pixel colors, a start cell (sr, sc), and a new color. Recolor the connected 4-direction component of cells that match the start pixel’s original color, then return the image. If the new color is already the same as the original, leave the image unchanged.

Example:

Input:

image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

Expected output:

[[2,2,2],[2,2,0],[2,0,1]]

Practice on LeetCode: Flood Fill

Golang Solution

Remember the start color. DFS through cells that still hold that color and paint them; bail out on bounds or a different color. Early-return when originalColor == color to avoid an infinite repaint loop.

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

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
    originalColor := image[sr][sc]

    if originalColor == color {
        return image
    }

    var dfs func(i, j int)

    dfs = func(i, j int) {
        if i < 0 || i >= len(image) ||
            j < 0 || j >= len(image[0]) {
            return
        }

        if image[i][j] != originalColor {
            return
        }

        image[i][j] = color

        dfs(i, j+1)
        dfs(i, j-1)
        dfs(i+1, j)
        dfs(i-1, j)
    }

    dfs(sr, sc)

    return image
}