733. Flood Fill - Detailed Explanation

Problem Statement

Given an m × n image represented by a 2D array image, a starting pixel coordinate (sr, sc), and a newColor, perform a “flood fill” on the image: replace the color of the starting pixel and all pixels connected 4‑directionally (up, down, left, right) that have the same original color with newColor. Return the modified image.

Examples

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

Explanation: Starting at pixel (1,1) with original color 1, all connected 1’s are repainted to 2.

Input:

image = [[0,0,0],
         [0,0,0]]
sr = 0, sc = 0, newColor = 0

Output:

[[0,0,0],
 [0,0,0]]

Explanation: newColor is the same as the original color, so no change.

Constraints

1 ≤ m, n ≤ 50
0 ≤ image[i][j], newColor < 2¹⁶
0 ≤ sr < m, 0 ≤ sc < n

Hints

If the starting pixel’s color already equals newColor, you can return immediately.
Use DFS or BFS to explore 4‑directionally connected pixels of the same original color.
Keep track of boundaries and avoid revisiting pixels by checking their color.

Approach 1 – DFS Recursion

Explanation

Record the origColor = image[sr][sc].
If origColor == newColor, return the image unchanged.
Define a recursive function dfs(r, c) that:
- Checks if (r,c) is out of bounds or image[r][c] != origColor; if so, returns.
- Sets image[r][c] = newColor.
- Calls itself on the four neighbors (r+1,c), (r-1,c), (r,c+1), (r,c-1).
Invoke dfs(sr, sc) and return the image.

Step‑by‑step Walkthrough

For the first example:

origColor = 1, newColor = 2
Start at (1,1):
  → paint (1,1) to 2
  → dfs(2,1): color=0 ≠ origColor, stop
  → dfs(0,1): paint to 2, recurse around it
  → dfs(1,2): color=0, stop
  → dfs(1,0): paint to 2, recurse...
Continue until all connected 1’s are repainted

Visual Example

Before:
1 1 1
1 1 0
1 0 1

Paint (1,1):
1 1 1      1 1 1
1 2 0  →   1 2 0
1 0 1      1 0 1

Expand to neighbors:
2 2 2
2 2 0
2 0 1

Python Implementation

Python3

. . . .

Approach 2 – BFS Iterative

Explanation

Use a queue to perform level‑order traversal:

If origColor == newColor, return immediately.
Initialize queue = deque([(sr, sc)]) and set image[sr][sc] = newColor.
While queue not empty:
- Pop (r,c).
- For each neighbor (nr, nc) in the four directions, if in bounds and image[nr][nc] == origColor, repaint it, enqueue it.
Return the image.

Python BFS Code

Python3

. . . .

Java Implementation (DFS)

Java

. . . .

Complexity Analysis

Time: O(m·n) – each pixel is visited at most once.
Space:
- DFS recursion uses O(m·n) stack in worst case.
- BFS queue uses O(m·n) extra space.

Common Mistakes

Not checking origColor == newColor first, causing infinite loops or unnecessary work.
Forgetting boundary checks, leading to index errors.
Repainting too early or too late (must repaint before enqueueing in BFS or before recursing in DFS).