Problem Statement

You are given a 2D integer array image representing an image, and three integers sr, sc, and newColor.

• (sr, sc) is the starting pixel.
• Flood fill the image starting from (sr, sc): replace the color of the starting pixel and all 4-directionally connected pixels with the same original color with newColor.

Return the modified image.

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

Constraints:

• 1 ≤ image.length, image[0].length ≤ 50
• 0 ≤ image[i][j], newColor ≤ 65535
• 0 ≤ sr < image.length
• 0 ≤ sc < image[0].length

---

Approach to Solve the Problem (Simple Language)

Idea:

• Flood fill is essentially a DFS or BFS traversal of connected pixels with the same color.
• Steps:

1. Store the original color of the starting pixel.
2. If newColor is the same as the original color, return image immediately (no changes needed).
3. Use DFS or BFS to visit all pixels 4-directionally connected that have the original color:
   • Change their color to newColor.
4. Return the updated image.

DFS Steps (Recursive):

1. Base case:
   • If current pixel is out of bounds, or color is different from original, return.
2. Change current pixel to newColor.
3. Recur in 4 directions: up, down, left, right.

---

Java Code Solution (DFS)

public class FloodFill {

    public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor != newColor) {
            dfs(image, sr, sc, originalColor, newColor);
        }
        return image;
    }

    private static void dfs(int[][] image, int r, int c, int color, int newColor) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
        if (image[r] != color) return;

        image[r] = newColor;

        // Explore 4 directions
        dfs(image, r + 1, c, color, newColor);
        dfs(image, r - 1, c, color, newColor);
        dfs(image, r, c + 1, color, newColor);
        dfs(image, r, c - 1, color, newColor);
    }

    public static void main(String[] args) {
        int[][] image = {
            {1,1,1},
            {1,1,0},
            {1,0,1}
        };
        int sr = 1, sc = 1, newColor = 2;
        int[][] result = floodFill(image, sr, sc, newColor);

        for (int[] row : result) {
            for (int val : row) System.out.print(val + " ");
            System.out.println();
        }
        // Output:
        // 2 2 2
        // 2 2 0
        // 2 0 1
    }
}

---

Dry Run Example

Input:

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

Step-by-step Execution:

1. Starting pixel: (1,1) → original color = 1
2. Change (1,1) to 2
3. Recur in 4 directions:

• Down (2,1) → color=0 → stop
• Up (0,1) → color=1 → change to 2, recur in its neighbors
• Right (1,2) → color=0 → stop
• Left (1,0) → color=1 → change to 2, recur in neighbors

4. Continue recursively until all connected 1s are changed to 2

Final Image:

[[2,2,2],
 [2,2,0],
 [2,0,1]]

---

Textual Diagram for Understanding

Start at (1,1) with color=1, newColor=2

Initial:
1 1 1
1 1 0
1 0 1

Step 1: change (1,1) → 2
Step 2: change neighbors with same color (1,0),(0,1),(0,0) → 2

Result:
2 2 2
2 2 0
2 0 1

---

Complexity Analysis

• Time Complexity: O(m * n)
  • m = number of rows, n = number of columns.
  • Each pixel is visited at most once.
• Space Complexity: O(m * n)
  • Recursive DFS stack can go as deep as number of pixels in the connected component.