Image Region Flood Fill

easyPROGraphsGraphs, Matrix, DFS/BFSCV - DSA

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 \leq sr < \text{image.length}$ and $0 \leq sc < \text{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

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]]

Reasoning

Inputs: image is a $3 \times 3$ grid of pixel colors, the seed is row $1$ , column $1$ , and newColor is $2$ . The seed pixel's color is $1$ , so the region to repaint is every pixel of color $1$ that can be reached from the seed by stepping up, down, left or right through color- $1$ pixels only.
Growing the region: from the center, the pixels above $(0,1)$ and to the left $(1,0)$ are $1$ , so they join. From those, the corners $(0,0)$ and $(0,2)$ and the pixel $(2,0)$ are also $1$ and join. The pixels $(1,2)$ and $(2,1)$ are $0$ , so they block the region.
The isolated $1$ : the bottom-right pixel $(2,2)$ has color $1$ , but its only neighbours are $(1,2)$ and $(2,1)$ , both $0$ . Diagonal contact with the center does not count, so it stays $1$ .
Output: the 6 reached pixels become $2$ , giving [[2,2,2],[2,2,0],[2,0,1]]. The $0$ pixels are untouched.
Notice: if newColor already equals the seed's color, nothing changes and the image is returned as it is.

More from CV - DSA

Concept primerPREVIEW

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

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.