733. Flood Fill


Problem Description

In this problem, we have a grid that represents an image, where each element in the grid is an integer that symbolizes the pixel value of the image. We're given a starting pixel defined by its row number sr and column number sc, and a new color value color. The task is to perform a "flood fill" on the image beginning from the starting pixel.

A flood fill is akin to pouring paint into a single spot and watching it spread out, coloring all connected areas with the same initial color. The fill spreads only in four directions: up, down, left, and right, from any given pixel. It continues to spread until it encounters a pixel with a different color than the starting pixel's original color.

The objective is to replace the color of the starting pixel and all connected pixels (4-directionally) with the same original color as the starting pixel with the new color. The end result is the image with the modified colors, which we should return.

Intuition

The intuitive approach to solving this problem is to simulate the flooding process using either Depth-First Search (DFS) or Breadth-First Search (BFS). Both are traversal algorithms that can navigate through the grid to find all pixels that are eligible for recoloring.

The intuition behind DFS is to start at the given pixel (sr, sc), change its color to the new color, and then recursively change the color of all adjacent pixels (up, down, left, right) that are the same color as the initial one. This does mean checking whether the new pixel position is within the boundary of the image and whether the pixel color matches the original color of the starting pixel.

For this solution, we'll use DFS:

  1. From the starting pixel, update its color to color.
  2. Look at adjacent pixels. For each adjacent pixel:
    • If the pixel is within bounds, and
    • If the pixel's color is the same as the starting pixel's original color, and
    • the pixel isn't already the new color (to prevent infinite recursion),
    • then recursively apply the flood fill to that pixel.

The recursive function spreads out from the initial pixel until it has reached all connected pixels with the original color, effectively performing the flood fill and updating the image as required.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution employs the Depth-First Search (DFS) algorithm, and the approach can be outlined in the following steps:

  1. Initial setup: We define a dfs helper function that will be used to perform the depth-first traversal and paint the image. The image matrix's dimensions are stored in m and n for convenience in bounds checking. The original color (oc) is recorded—it's the color of the starting pixel (at sr, sc).

  2. Defining directions: A tuple named dirs is defined, which includes the relative positions that represent the 4-directional moves: up, down, left, and right. The tuple has the pattern (-1, 0, 1, 0, -1) in order to easily loop through pairs of directions for up-down-left-right traversal.

  3. Recursion with DFS: The dfs function takes a position (i, j):

    • It checks if the current position is out of bounds or if the pixel's color is not the same as the original color (oc) or is already painted with the new color—this is the base case for the recursion to stop or prevent infinite loops.
    • If the base case does not hold, the current pixel's color is changed to the color.
    • For each 4-directional neighbor (calculated using the dirs tuple), apply DFS recursion by calling dfs on the neighbor's coordinates.
    1def dfs(i, j):
    2    if (
    3        not 0 <= i < m
    4        or not 0 <= j < n
    5        or image[i][j] != oc
    6        or image[i][j] == color
    7    ):
    8        return
    9    image[i][j] = color
    10    for a, b in pairwise(dirs):
    11        dfs(i + a, j + b)

    In the implementation, pairwise(dirs) construct is used (assuming it's similar to Python's pairwise utility to make pairs from the dirs tuple), which should create pairs of directions we want to move in (up, down, left, and right). There is a detail here: most Python environments do not have a built-in function called pairwise. Hence, it's likely meant to be a custom utility defined somewhere else, or an import from some module like itertools. For example, if it was intended as itertools.pairwise(), we would need to import itertools and make sure to handle the last repetitive direction.

  4. Initiating the fill: The DFS recursion is initiated by calling dfs(sr, sc).

  5. Returning the result: After DFS completes, it returns the image, which by now has been flood-filled using the new color.

The DFS recursion ensures that all connected pixels of the same original color have been recolored, and as the recursion unwinds, the modified image is eventually returned.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's consider a small grid as our example image, where we will apply the flood fill algorithm. Suppose the image is a 3x3 grid as follows:

11 1 2
21 1 0
31 0 3

The starting pixel for our flood fill is defined by the row number sr = 1 and column number sc = 1 (using 0-based indexing), and the new color we want to apply is 2.

The pixel at (1, 1) has the color 1. According to the flood fill algorithm, we want to change this color and all connected pixels of the same color to 2.

Step 1: We start from the pixel at (1, 1). Its color is 1, which matches the original color (hence eligible for color change). We change its color to 2.

Our image now looks like this:

11 1 2
21 2 0
31 0 3

Step 2: We perform DFS from our starting pixel. We look at its four neighbors: up (0, 1), down (2, 1), left (1, 0), and right (1, 2).

  • Pixel (0, 1) has color 1, so it is eligible. We fill it with color 2.
  • Pixel (2, 1) has color 0 and is not eligible since it is not the original color.
  • Pixel (1, 0) has color 1, so it is eligible. We fill it with color 2.
  • Pixel (1, 2) has color 0 and is not eligible since it is not the original color.

Now our image looks like this:

11 2 2
22 2 0
31 0 3

Step 3: We now apply DFS on the neighbors of these newly colored pixels (0, 1) and (1, 0).

  • Checking neighbors of (0, 1): The up and down directions are out of bounds, the left pixel (0, 0) with color 1 gets filled, and the right pixel (0, 2) has color 2.

  • Checking neighbors of (1, 0): All sides except the left pixel (1, -1), which is out of bounds, have already been checked or don't have the original color.

Our final image now looks like this:

12 2 2
22 2 0
31 0 3

The image has been successfully filled using the new color 2, starting from the pixel at (1, 1). Pixels connected with the same original color have been recolored, illustrating how the flood fill algorithm works.

Solution Implementation

1from typing import List
2
3class Solution:
4    def floodFill(self, image: List[List[int]], start_row: int, start_col: int, new_color: int) -> List[List[int]]:
5        """
6        Perform a flood fill on the image starting from the pixel at (start_row, start_col), changing all
7        connected pixels of the same color to the new color.
8
9        :param image: 2-D array representing the image.
10        :param start_row: The row of the starting pixel.
11        :param start_col: The column of the starting pixel.
12        :param new_color: The new color to apply to the connected pixels.
13        :return: The image after the flood fill operation.
14        """
15        def flood_fill_helper(row: int, col: int):
16            # If the pixel is out of bounds, not the original color, or already the new color,
17            # then do not proceed with the fill
18            if (not 0 <= row < height or not 0 <= col < width or
19                    image[row][col] != original_color or image[row][col] == new_color):
20                return
21          
22            # Change the pixel to the new color
23            image[row][col] = new_color
24          
25            # Visit all four adjacent pixels (up, right, down, left)
26            for delta_row, delta_col in zip(directions[:-1], directions[1:]):
27                flood_fill_helper(row + delta_row, col + delta_col)
28
29        # Define the directions for moving to adjacent pixels
30        directions = [-1, 0, 1, 0, -1]
31        # Get the dimensions of the image
32        height, width = len(image), len(image[0])
33        # Get the original color of the starting pixel
34        original_color = image[start_row][start_col]
35      
36        # Begin the flood fill from the starting pixel
37        flood_fill_helper(start_row, start_col)
38      
39        return image
40
1class Solution {
2 
3    // Direction vectors representing the 4 connected pixels (up, right, down, left).
4    private int[] directions = {-1, 0, 1, 0, -1};
5    // The image we need to modify.
6    private int[][] image;
7    // The new color to apply to the flood fill.
8    private int newColor;
9    // The original color to be replaced.
10    private int originalColor;
11
12    // Method to begin flood fill operation
13    public int[][] floodFill(int[][] image, int startRow, int startColumn, int color) {
14        // Initialize the image, new color, and original color based on the input.
15        this.image = image;
16        this.newColor = color;
17        this.originalColor = image[startRow][startColumn];
18      
19        // Call the recursive dfs method starting from the pixel at (sr, sc)
20        dfs(startRow, startColumn);
21        // Return the modified image after the flood fill operation.
22        return image;
23    }
24
25    // Depth-first search (DFS) method to apply new color to connected components.
26    private void dfs(int row, int column) {
27        // Boundary check: if the pixel is out of bounds or isn't the original color or is already the new color, return.
28        if (row < 0 || row >= image.length || column < 0 || column >= image[0].length || 
29            image[row][column] != originalColor || image[row][column] == newColor) {
30            return;
31        }
32      
33        // Change the color of the current pixel to the new color.
34        image[row][column] = newColor;
35      
36        // Iterate through each of the 4 connected neighbors.
37        for (int k = 0; k < 4; ++k) {
38            // Recursively call dfs for the current neighbor.
39            dfs(row + directions[k], column + directions[k + 1]);
40        }
41    }
42}
43
1#include <vector>
2#include <functional>
3
4class Solution {
5public:
6    // Method to perform flood fill algorithm.
7    vector<vector<int>> floodFill(vector<vector<int>>& image, int startRow, int startCol, int newColor) {
8        int rowCount = image.size();
9        int colCount = image[0].size();
10        int oldColor = image[startRow][startCol];
11      
12        // Directions to move in the matrix - up, right, down, left
13        int directions[5] = {-1, 0, 1, 0, -1};
14
15        // Define depth-first search lambda function to apply the new color recursively
16        std::function<void(int, int)> dfs = [&](int row, int col) {
17            // Check for out-of-bounds, if the color is different from the oldColor, or if it's already filled with the newColor
18            if (row < 0 || row >= rowCount || col < 0 || col >= colCount || image[row][col] != oldColor || image[row][col] == newColor) {
19                return;
20            }
21            // Apply the new color
22            image[row][col] = newColor;
23            // Perform DFS in all directions
24            for (int k = 0; k < 4; ++k) {
25                dfs(row + directions[k], col + directions[k + 1]);
26            }
27        };
28
29        // Start the flood fill from the (startRow, startCol)
30        dfs(startRow, startCol);
31        return image; // Return the modified image
32    }
33};
34
1/**
2 * Performs a flood fill on an image starting from the pixel at (sr, sc).
3 *
4 * @param {number[][]} image - The 2D array of numbers representing the image.
5 * @param {number} sr - The row index of the starting pixel.
6 * @param {number} sc - The column index of the starting pixel.
7 * @param {number} newColor - The color to fill with.
8 * @returns {number[][]} - The modified image after performing the flood fill.
9 */
10function floodFill(image: number[][], sr: number, sc: number, newColor: number): number[][] {
11    // Determine the dimensions of the image
12    const rowCount = image.length;
13    const colCount = image[0].length;
14  
15    // Target color to replace
16    const targetColor = image[sr][sc];
17
18    /**
19     * Recursive depth-first search function to perform the color fill.
20     *
21     * @param {number} row - The current row index.
22     * @param {number} col - The current column index.
23     */
24    function dfs(row: number, col: number): void {
25        // Check if the current pixel is outside the image boundaries,
26        // already has the new color, or is not matching the target color.
27        if (
28            row < 0 || row === rowCount ||
29            col < 0 || col === colCount ||
30            image[row][col] !== targetColor ||
31            image[row][col] === newColor
32        ) {
33            // Exit the function without further processing.
34            return;
35        }
36
37        // Fill the current pixel with the new color.
38        image[row][col] = newColor;
39
40        // Recursively apply the fill operation to the neighboring pixels.
41        dfs(row + 1, col); // Down
42        dfs(row - 1, col); // Up
43        dfs(row, col + 1); // Right
44        dfs(row, col - 1); // Left
45    }
46
47    // Call the dfs function on the starting pixel.
48    dfs(sr, sc);
49
50    // Return the updated image after the flood fill.
51    return image;
52}
53

Time and Space Complexity

The time complexity of the flood fill algorithm is O(M*N), where M is the number of rows and N is the number of columns in the image. This is because in the worst case, the algorithm performs a depth-first search (DFS) on every cell in the grid once when the entire image requires to be filled with the new color.

The space complexity is also O(M*N), primarily due to the recursive stack that could potentially grow to the size of the entire grid in the case of a large connected region with the same color that needs to be filled.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄