Problem

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

OR

Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.

Examples

Example 1:

$$ \begin{bmatrix} 1 & 1 & 1 \\ 1 & \colorbox{red} 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} \Longrightarrow \begin{bmatrix} 2 & 2 & 2 \\ 2 & 2 & 0 \\ 2 & 0 & 1 \end{bmatrix} $$

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] ]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2:

Input: image = [ [0,0,0],[0,0,0] ], sr = 0, sc = 0, color = 0
Output: [ [0,0,0],[0,0,0] ]
Explanation: The starting pixel is already colored 0, so no changes are made to the image.

Solution

The problem described is a classic example of the Flood Fill algorithm, commonly used in image editing software to fill a region with a particular color.

Method 1 - DFS

  • Base case: the point is at the border. Do nothing.
  • Recursion: check the up, down, left and right point to see if we can fill in.

Code

Java
public class FloodFill {

	public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		int originalColor = image[sr][sc];

		// Base case to avoid infinite loop
		if (originalColor == newColor) {
			return image;
		}

		dfs(image, sr, sc, originalColor, newColor);
		return image;
	}

	private static void dfs(int[][] image, int x, int y, int originalColor, int newColor) {
		// Check for boundary conditions and ensure the current pixel matches the original color
		if (x < 0 || y < 0 || x >= image.length || y >= image[0].length || image[x][y] != originalColor) {
			return;
		}

		// Replace the current pixel color with the new color
		image[x][y] = newColor;

		// Recursive calls for all 4 directions
		dfs(image, x + 1, y, originalColor, newColor);
		dfs(image, x - 1, y, originalColor, newColor);
		dfs(image, x, y + 1, originalColor, newColor);
		dfs(image, x, y - 1, originalColor, newColor);
	}
}
Python
def flood_fill(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]

    # Base case to avoid infinite loop
    if original_color == color:
        return image

    def dfs(x: int, y: int) -> None:
        if x < 0 or y < 0 or x >= rows or y >= cols or image[x][y] != original_color:
            return

        image[x][y] = color

        # Recursive calls for all 4 directions
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)

    dfs(sr, sc)
    return image

Complexity

  • ⏰ Time complexity: O(m*n), where m is the number of rows and n is the number of columns
  • 🧺 Space complexity: O(m*n)