Image Region Flood Fill
Image segmentation often begins by identifying spatially contiguous regions of similar features or colors. The Flood Fill algorithm is a classic graph traversal technique (typically implemented via Depth-First Search or Breadth-First Search) used to select and modify such a connected area starting from a specific point.
You are given a 2D integer array image representing a digital image. Each integer represents a pixel value (intensity). Given a starting pixel at coordinates (sr, sc) and a newColor, perform a "flood fill" on the image.
The flood fill operation should target the starting pixel, plus any pixels connected 4-directionally (horizontal or vertical) to the starting pixel that share the original color, and so on recursively. All targeted pixels must have their color replaced with newColor. You must return the modified image array.
Constraints:
- The length of image and image[i] will be in the range [1,50].
- The given starting pixel will satisfy 0≤sr<image.length and 0≤sc<image[0].length.
- The value of each color in image[i][j] and newColor will be an integer in [0,65535].
- If the original color is the same as the newColor, no action should be taken to prevent infinite recursion/loops.
Example:
image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1 newColor = 2
[[2,2,2],[2,2,0],[2,0,1]]
Starting pixel is (1, 1) with color 1. All connected pixels with color 1 are changed to color 2.
Image Region Flood Fill: Comprehensive Background & Solution Guide
1. Background Knowledge
Flood Fill is a fundamental graph traversal algorithm used in computer graphics and image processing to identify and modify 4-connected (or 8-connected) regions of similar pixel values. Treat the image as a graph where each pixel is a node, and edges connect adjacent pixels (up, down, left, right for 4-connectivity).
Key Prerequisites:
- Graph traversal: Understand DFS (stack-based, recursive) vs BFS (queue-based, iterative)
- Connected components: Pixels sharing the same value and connected via specified directions form one component
- Boundary conditions: Handle image edges and prevent out-of-bounds access
- Color matching: Only fill pixels matching the original color at starting position (sr, sc)
The algorithm originates from paint bucket tools and is widely used in image segmentation.
2. Algorithm Approach
Two primary implementations:
| Approach | Data Structure | Characteristics | Use Case |
|---|---|---|---|
| DFS (Recursive) | Call stack | Simple, intuitive; risk of stack overflow for large regions | Small images (≤50×50 per constraints) |
| BFS (Iterative) | Queue | Memory efficient, no recursion limit | Preferred for production code |
Core Logic: Start from (sr, sc), replace matching pixels with newColor, and recursively/iteratively explore 4-neighbors.
Early Termination: If image[sr][sc] == newColor, return unchanged image to avoid infinite loops.
3. Step-by-Step Strategy
1. Store original_color = image[sr][sc]
2. If original_color == newColor, return image unchanged
3. Initialize queue/stack with (sr, sc)
4. While queue/stack not empty:
a. Dequeue/pop current (r, c)
b. If image[r][c] != original_color, skip (already processed)
c. Set image[r][c] = newColor
d. Enqueue/push valid 4-neighbors: (r-1,c), (r+1,c), (r,c-1), (r,c+1)
5. Return modified image
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.