
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:
- Changing the color of the starting pixel to the new specified
color
. - Propagating this change to directly adjacent pixels (horizontally or vertically), provided they match the starting pixel's original color.
- 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:
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.
- Start at the pixel
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.
- Use a recursive or iterative approach to apply the target
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.
- Ensure that you do not revisit pixels that have already been changed to the new
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.
- The constraints limit the dimensions of the grid (
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
- Java
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);
}
}
}
}
In this Java solution for the Flood Fill problem, the aim is to change the color of an image starting from a given pixel (sr, sc)
(start row and start column) to a new color, newColor
. The process should only affect the areas connected to the initial pixel that have the same original color.
The main logic resides in the floodFill
method, within the Solution
class. This method first reads the original color of the starting pixel and checks if it's the same as the new color. If they are not the same, a recursive helper function fill
is called to apply the new color to the connected pixels.
The fill
method checks whether the current pixel matches the old color:
- If true, it sets this pixel to the new color.
- It then recursively applies the same logic to neighboring pixels (i.e., left, right, up, and down) but ensures bounds are respected to prevent accessing out-of-range array indexes.
Consider using this approach in applications where recursive depth isn't an issue and ensure sufficient stack memory for large images to avoid a stack overflow error. This solution guarantees that only the connected component of pixels with a matching color will be repainted, which is useful for scenarios like paint-fill tools in graphics applications.
No comments yet.