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

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

Approach 1 – DFS Recursion

Explanation

1. Record the origColor = image[sr][sc].
2. If origColor == newColor, return the image unchanged.
3. 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).
4. 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