Domain 1EasyCORE

Flood Fill

The problem requires us to perform a flood fill operation on a 2-D array representing an image. The flood fill starts at a given coordinate `(sr, sc)` and changes all pixels connected 4-directionally (up, down, left, right) that have the same initial color as the starting pixel to a new specified color `newColor`. The task is to return the modified image.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Depth-first Search

733. Flood Fill

Model: qwen2.5-coder:14b
Topics: Depth-first Search
FAANG asked: 1
Acceptance rate: 56.0%


Problem Breakdown

The problem requires us to perform a flood fill operation on a 2-D array representing an image. The flood fill starts at a given coordinate (sr, sc) and changes all pixels connected 4-directionally (up, down, left, right) that have the same initial color as the starting pixel to a new specified color newColor. The task is to return the modified image.

Inputs:

  • image: A 2-D array of integers where each integer represents a pixel value.
  • sr and sc: Coordinates of the starting pixel for the flood fill.
  • newColor: The new color to apply during the flood fill.

Outputs:

  • Modified 2-D array with the flood fill applied.

Implicit Constraints or Tricky Edge Cases:

  • If the starting pixel is already the same as newColor, no changes should be made.
  • The image dimensions are within [1, 50].
  • Pixel values range from [0, 65535].

Intuition

The brute-force approach would involve checking each pixel in the image to see if it is connected to the starting pixel and changing its color if it is. This approach is inefficient because it may require checking every pixel multiple times.

A more efficient approach involves using Depth-First Search (DFS) or Breadth-First Search (BFS). The key insight is that we can explore all connected pixels of the same color starting from the initial pixel and change their colors in a recursive manner. This ensures that each pixel is visited only once, leading to a more optimal solution.

Approach

We will use Depth-First Search (DFS) to solve this problem. Here are the steps:

  1. Base Case Check: If the starting pixel’s color is already newColor, return the image as no changes are needed.
  2. Recursive DFS Function: Define a helper function that performs the DFS:
    • Change the current pixel’s color to newColor.
    • Recursively apply the same logic to all 4-directionally connected pixels (up, down, left, right) that have the same initial color as the starting pixel.
  3. Initial Call: Start the DFS from the given coordinates (sr, sc).

Complexity Analysis

  • Time Complexity: O(n), where n is the number of pixels in the image. Each pixel is visited at most once.
  • Space Complexity: O(n) due to the recursion stack in the worst case when all pixels are connected and need to be processed.

Solution

def floodFill(image, sr, sc, newColor):
    # Get the initial color of the starting pixel
    initial_color = image[sr][sc]
    
    # If the initial color is already the new color, no changes needed
    if initial_color == newColor:
        return image
    
    # Define the DFS helper function
    def dfs(r, c):
        # Change the current pixel's color to newColor
        image[r][c] = newColor
        
        # Explore all 4-directionally connected pixels
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            # Check if the new coordinates are within bounds and have the initial color
            if 0 <= nr < len(image) and 0 <= nc < len(image[0]) and image[nr][nc] == initial_color:
                dfs(nr, nc)
    
    # Start DFS from the given starting pixel
    dfs(sr, sc)
    
    return image

Edge Cases Handled

  • Already Filled: If the starting pixel’s color is already newColor, the function returns immediately without making any changes.
  • Single Pixel Image: The algorithm works correctly even if the image consists of a single pixel.
  • Disconnected Components: The DFS ensures that only pixels connected to the starting pixel are changed, leaving other components unchanged.