Flood Fill
Easy
You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc].
To perform a flood fill:
- Begin with the starting pixel and change its color to
color. - Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel.
- Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel.
- The process stops when there are no more adjacent pixels of the original color to update.
Return the modified image after performing the flood fill.
Example:
Consider the following image: [[1,1,1],[1,1,0],[1,0,1]]. If we start at sr = 1, sc = 1, and want to change the color to color = 2, the expected output is [[2,2,2],[2,2,0],[2,0,1]]. The algorithm starts at the center pixel (value 1) and changes it to 2. Then, it recursively updates all adjacent pixels with the original color (1) to the new color (2). The bottom corner is not updated because it is not connected to the starting pixel via a path of 1's.
How would you implement an efficient algorithm to solve the flood fill problem, taking into consideration time and space complexity, and potential edge cases?
Solution
Naive (Brute Force) Solution
A brute-force approach to solving the flood fill problem would involve recursively checking all adjacent pixels and changing their color if they match the original color. This method is straightforward but may lead to stack overflow errors for very large images due to excessive recursion.
Algorithm
- Check if the starting pixel's color matches the new color. If so, return the original image.
- Implement a recursive function that takes the image, row index, column index, original color, and new color as input.
- In the recursive function:
- Check for out-of-bounds conditions or if the current pixel's color doesn't match the original color. If any of these conditions are true, return.
- Change the current pixel's color to the new color.
- Recursively call the function for the four adjacent pixels (up, down, left, right).
Code (Python)
def floodFill_brute_force(image, sr, sc, color):
if image[sr][sc] == color:
return image
def fill(image, r, c, original_color, new_color):
if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]) or image[r][c] != original_color:
return
image[r][c] = new_color
fill(image, r + 1, c, original_color, new_color)
fill(image, r - 1, c, original_color, new_color)
fill(image, r, c + 1, original_color, new_color)
fill(image, r, c - 1, original_color, new_color)
original_color = image[sr][sc]
fill(image, sr, sc, original_color, color)
return image
Big O Analysis (Brute Force)
- Time Complexity: O(m * n) in the worst case, where m is the number of rows and n is the number of columns in the image. This is because, in the worst case, we might need to visit every pixel in the image.
- Space Complexity: O(m * n) in the worst case due to the recursive call stack. This can be significant for large images.
Optimal Solution
The optimal solution also uses a recursive approach (Depth-First Search), but it's crucial to manage the recursion effectively to avoid stack overflow issues. The algorithm remains the same but is optimized for clarity and efficiency.
Algorithm
- Check if the starting pixel's color matches the new color. If so, return the original image.
- Implement a recursive function that takes the image, row index, column index, original color, and new color as input.
- In the recursive function:
- Check for out-of-bounds conditions or if the current pixel's color doesn't match the original color. If any of these conditions are true, return.
- Change the current pixel's color to the new color.
- Recursively call the function for the four adjacent pixels (up, down, left, right).
Code (Python)
def floodFill(image, sr, sc, color):
if image[sr][sc] == color:
return image
rows, cols = len(image), len(image[0])
original_color = image[sr][sc]
def dfs(row, col):
if row < 0 or row >= rows or col < 0 or col >= cols or image[row][col] != original_color:
return
image[row][col] = color
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
dfs(sr, sc)
return image
Big O Analysis (Optimal)
- Time Complexity: O(m * n) in the worst case, where m is the number of rows and n is the number of columns in the image. This is because, in the worst case, we might need to visit every pixel in the image.
- Space Complexity: O(m * n) in the worst case due to the recursive call stack. In practice, this is often less than O(m*n) because we only recurse on pixels that match the starting color.
Edge Cases
- Starting Pixel Already the Target Color: If the starting pixel's color is the same as the new color, no changes should be made to the image. The code handles this case by returning immediately.
- Image Dimensions: The code should correctly handle images of various sizes, including very small or very large images.
- Different Colors: The code should work correctly for any valid color values within the specified constraints.
- Empty Image: Although the constraints specify that
1 <= m, n <= 50, the code should ideally handle an empty image gracefully (though this is not strictly required by the problem description).
Summary
The flood fill algorithm is effectively implemented using Depth-First Search (DFS). The key is to recursively update adjacent pixels of the same color until no more updates are possible. The time complexity is O(m * n), and the space complexity depends on the depth of the recursion, which in the worst case can be O(m * n).
