Flood Fill

Problem Statement

In this task, you are provided with a digital image expressed as a 2D grid of integer values, where each integer represents a pixel's color. Additionally, you are given a specific pixel location, denoted by (sr, sc), where sr is the pixel's row index and sc is the column index, along with a target color value. Your objective is to modify the color of the specified starting pixel and recursively spread this change to its adjacent pixels. The adjustment should continue as long as the neighboring pixels have the same original color as the initially selected pixel.

The flooding process entails:

1. Changing the color of the starting pixel to the new specified color.
2. Propagating this change to directly adjacent pixels (horizontally or vertically), provided they match the starting pixel's original color.
3. The changes proliferate outwards from the initial pixel and continue until no adjacent pixels with the matching original color remain.

The task culminates when you return the altered image, demonstrating all the color changes triggered by the initial flood fill operation.

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 of the image with position `(sr, sc) = (1, 1)` (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.

Note the bottom corner is not colored 2, because it is not horizontally or vertically 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 is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.

Constraints

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

Approach and Intuition

To address the problem effectively, let's dissect the process based on the given examples and constraints. The flood fill algorithm is best visualized as coloring in a contiguous area on a grid, much like using a paint bucket tool in graphics software. Here's the approach, broken down:

1. Identify the initial conditions:

   • Start at the pixel image[sr][sc] and note its original color.
   • If the target color is the same as the current pixel's color, no changes need to be done. This observation directly leads to an optimization point where the algorithm can terminate early, as seen in Example 2.

2. Flood fill implementation:

   • Use a recursive or iterative approach to apply the target color. Typically, a Depth-First Search (DFS) is appropriate for this kind of task.
   • Begin the filling process from the starting pixel. If the current pixel's color matches the original color, change it to the new color.
   • Recursively apply the above step to the 4 neighbors (left, right, top, bottom) of the current pixel, checking bounds to avoid accessing outside of the grid.

3. Special cases handling:

   • Ensure that you do not revisit pixels that have already been changed to the new color or fall outside the image boundaries.
   • Stop the spreading of the color when there are no adjacent qualifying pixels left, effectively understanding when to cease the recursive process.

4. Performance considerations:

   • The constraints limit the dimensions of the grid (1 <= m, n <= 50), making a recursive solution feasible without excessive risk of stack overflow.
   • Given each pixel might be checked at most four times (from each of its four possible neighbors), the overall complexity remains manageable within the provided constraints.

This method ensures that all areas of the image that are connected and share the initial color are replaced with the new color, simulating a flood fill effect as efficiently as possible given the operational constraints.

Solutions

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor != newColor) {
            fill(image, sr, sc, oldColor, newColor);
        }
        return image;
    }
    public void fill(int[][] image, int r, int c, int oldColor, int newColor) {
        if (image[r][c] == oldColor) {
            image[r][c] = newColor;
            if (r >= 1) {
                fill(image, r - 1, c, oldColor, newColor);
            }
            if (c >= 1) {
                fill(image, r, c - 1, oldColor, newColor);
            }
            if (r + 1 < image.length) {
                fill(image, r + 1, c, oldColor, newColor);
            }
            if (c + 1 < image[0].length) {
                fill(image, r, c + 1, oldColor, newColor);
            }
        }
    }
}