Flood Fill

Flood Fill

You are given 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 color.

Perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill:

1. Begin with the starting pixel and change its color to color.
2. Perform the same process for each pixel that is directly adjacent (up, down, left, right) and shares the same original color as the starting pixel.
3. 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.

Return the modified image after performing the flood fill.

Examples

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center pixel (1,1) with color 1, all
adjacent pixels of the same color are changed to 2.
Note the bottom-right 1 is not changed 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, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation: The starting pixel already has the target color,
so no changes are made.

Example 3:

Input: image = [[0,0,0],[0,1,1]], sr = 1, sc = 1, color = 1
Output: [[0,0,0],[0,1,1]]
Explanation: The starting pixel already has color 1 which is
the same as the new color, so the image is unchanged.

Constraints

• m == image.length
• n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], color < 2^16
• 0 <= sr < m
• 0 <= sc < n

Expected Complexity

• Time: O(m * n). each pixel is visited at most once
• Space: O(m * n). recursion stack in the worst case