We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Flood Fill

Number: 733

Difficulty: Easy

Paid? No

Companies: Amazon, Microsoft, Meta, Bloomberg, Google, Goldman Sachs, Apple, Uber

Problem Description

Given an m x n grid representing an image, where each cell represents a pixel's color, perform a flood fill starting from a given starting pixel (sr, sc). Change the starting pixel's color to a new given color, and then change all directly adjacent pixels (up, down, left, right) that have the same original color recursively. Stop when there are no more adjacent pixels with the original color.

Key Insights

  • The flood fill operation can be executed using either DFS (Depth First Search) or BFS (Breadth First Search).
  • A check is needed at the beginning to determine if the new color is the same as the original; if so, no changes are needed.
  • The algorithm recursively or iteratively visits each pixel that is directly adjacent and matches the original color, then updates its color.
  • The problem has a worst-case scenario where all pixels are the same color, leading to a full traversal of the grid.

Space and Time Complexity

Time Complexity: O(m * n), where m and n are the dimensions of the image grid, because in the worst-case all cells are visited. Space Complexity: O(m * n) in the worst-case due to the recursion stack (or BFS queue) if the entire image needs to be filled.

Solution

We use a DFS approach to perform the flood fill. The algorithm starts at the given starting pixel and uses recursion to fill connected pixels with the same original color. The following steps are key:

  1. Check if the starting pixel's color is already the target color; if so, return the image immediately.
  2. Define a recursive helper function that:
    • Checks boundary conditions.
    • Updates the current pixel's color.
    • Recursively calls itself on the four adjacent directions (up, down, left, right).
  3. Return the modified image after the recursion completes.

Data structures used:

  • Recursion call stack for the DFS implementation.
  • Variables to store the image dimensions and original color.

Code Solutions

def floodFill(image, sr, sc, color):
    # Get the original color of the starting pixel
    orig_color = image[sr][sc]
    # If the new color is the same as the original, return the image as is
    if orig_color == color:
        return image
    rows, cols = len(image), len(image[0])
    
    # Recursive DFS helper function to fill the image
    def dfs(r, c):
        # Check boundaries and if the current pixel is the same as the original color
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != orig_color:
            return
        # Update the current pixel's color
        image[r][c] = color
        # Recursively call DFS in all four directions
        dfs(r - 1, c)  # up
        dfs(r + 1, c)  # down
        dfs(r, c - 1)  # left
        dfs(r, c + 1)  # right
    
    dfs(sr, sc)
    return image
← Back to All Questions