Flood Fill - Leetcode Solution

The Flood Fill problem on LeetCode is a classic problem in computer graphics. The problem involves filling in a region of an image with a given color. In this article, we will explain the problem and provide a detailed solution.

Problem Statement:

Given an image represented by a 2D integer array, and the location of a pixel (x, y) in the image, you need to change the color of the pixel to a new color newColor, and then recursively fill the neighboring pixels of the same old color to the new color until all the pixels in the region are filled with the new color.

Solution:

The problem can be solved using Depth First Search (DFS) or Breadth First Search (BFS). We will use DFS to solve this problem.

Step 1: Check the base case:

If the source pixel (x, y) has already been filled with the new color or if the source pixel is not of the old color, then we do not need to fill the region and we can return the image as is.

Step 2: Update the source pixel:

Change the color of the source pixel (x, y) to the new color newColor.

Step 3: Recursive Flood Fill:

We can now recursively fill the neighboring pixels of the same old color to the new color using DFS.

Consider the current pixel (x, y) in the image. We can check its neighboring pixels to see if they need to be filled or not. We only need to check the pixels that are within the bounds of the image and are of the old color. To ensure that we check each and every pixel in the region, we will perform the DFS in all four directions - top, right, bottom, and left.

We will use a recursive function for the DFS. The function will take the image, the coordinates of the current pixel (x, y), the old color, and the new color as inputs. We will also use an auxiliary function to check if a pixel is within the bounds of the image.

Here is the algorithm for the Flood Fill problem using DFS:

1. Create a function called 'FloodFill' that takes the image, the coordinates of the current pixel (x, y), the old color, and the new color as inputs.

2. Check the base case:

   a. If the pixel (x, y) is out of bounds or has already been filled with the new color or is not of the old color, return the image.

3. Update the source pixel (x, y) to the new color newColor.

4. Recursively fill the neighboring pixels of the same old color to the new color using DFS:

   a. Call the FloodFill function on the pixel to the top of (x, y). b. Call the FloodFill function on the pixel to the right of (x, y). c. Call the FloodFill function on the pixel to the bottom of (x, y). d. Call the FloodFill function on the pixel to the left of (x, y).

5. Return the image.

Here is the Python code for the Flood Fill problem using DFS:

def FloodFill(image, x, y, oldColor, newColor):
    # check if the pixel is out of bounds or has already been filled with new color
    if (not withinBounds(image, x, y)) or image[x][y] == newColor or image[x][y] != oldColor:
        return image
    
    # update the source pixel to new color
    image[x][y] = newColor
    
    # recursively fill the neighboring pixels of the same old color to the new color using DFS
    FloodFill(image, x-1, y, oldColor, newColor)  # top
    FloodFill(image, x, y+1, oldColor, newColor)  # right
    FloodFill(image, x+1, y, oldColor, newColor)  # bottom
    FloodFill(image, x, y-1, oldColor, newColor)  # left
    
    return image


def withinBounds(image, x, y):
    # check if the pixel is within the bounds of the image
    if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]):
        return False
    return True

Time and Space Complexity:

The time complexity of the algorithm is O(m * n) where m and n are the dimensions of the image. This is because we visit each pixel in the image only once.

The space complexity of the algorithm is O(m * n) where m and n are the dimensions of the image. This is because we use a recursive function and each call to the function creates a new stack frame which takes up memory. In the worst case, all the pixels in the image can be part of the same region and we will need to create a stack frame for each pixel.

1