algoadvance

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the pixel with value 1),
all pixels connected by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
Output: [[2,2,2],[2,2,2]]

Constraints:

Clarifying Questions

  1. Should we perform the flood fill if the starting pixel is already the new color? No, there is no need to perform the flood fill if the starting pixel is already of the new color, as it won’t change anything in the image.
  2. Is it guaranteed that the given indices sr and sc are within the bounds of the image? Yes, the constraints guarantee that 0 <= sr < m and 0 <= sc < n.

Strategy

We will use Depth-First Search (DFS) to perform the flood fill. Here are the detailed steps:

  1. Check if the starting pixel image[sr][sc] is already equal to the newColor. If it is, simply return the image as no changes are needed.
  2. Otherwise, store the original color of the starting pixel.
  3. Use a recursive DFS function to visit each pixel that has the same original color and change it to the newColor.
  4. Handle the recursion by stopping when encountering a pixel that is out of bounds or not of the original color.

Code

def floodFill(image, sr, sc, newColor):
    def dfs(r, c):
        if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]) or image[r][c] != originalColor:
            return
        image[r][c] = newColor
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    
    originalColor = image[sr][sc]
    if originalColor == newColor:
        return image
    
    dfs(sr, sc)
    return image

# Example usage:
image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
sr = 1
sc = 1
newColor = 2
print(floodFill(image, sr, sc, newColor))  # Output: [[2, 2, 2], [2, 2, 0], [2, 0, 1]]

Time Complexity

The time complexity is O(m * n) where m is the number of rows and n is the number of columns in the image. In the worst-case scenario, every pixel might need to be visited and colored.

This solution is efficient given the constraints.

Try our interview co-pilot at AlgoAdvance.com