Flood Fill easy

Problem Statement

An image is represented by an m x n integer array image where image[i][j] represents the pixel value of the image.

You are given an integer array sr representing the row index and sc representing the column index of the starting pixel.

You are also given an integer newColor.

You should perform a flood fill on the image starting from the pixel (sr, sc).

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all these connected pixels with newColor.

Return the modified image.

Example 1

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: From the center of the image (with the value of 1), all connected 1s will be changed to 2. Note that only connected pixels of value 1 are changed.

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2

Output: [[2,2,2],[2,2,2]]

Steps

1. Base Case: If the starting pixel's color is already the newColor, return the image as no change is needed.
2. Depth-First Search (DFS): Use a recursive or iterative DFS approach to traverse all connected pixels of the same color as the starting pixel.
3. Mark Visited Pixels: Keep track of visited pixels to avoid infinite loops. You can either modify the original image in-place (setting the color to newColor as you visit) or use a separate visited array. In-place modification is more efficient in terms of space.
4. Explore Neighbors: For each pixel, explore its four neighbors (up, down, left, right). If a neighbor has the same color as the starting pixel and hasn't been visited, recursively/iteratively call the DFS function on it.
5. Return Modified Image: After the DFS is complete, return the modified image.

Explanation

The solution uses Depth-First Search (DFS) to explore connected components of pixels with the same initial color. DFS is a graph traversal algorithm suitable for exploring connected components. We recursively visit neighboring pixels with the same color, changing their color to newColor as we go. The base case handles the situation where no change is necessary, and we use boundary checks to prevent out-of-bounds array accesses.

Code

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image;

        int rows = image.Length;
        int cols = image[0].Length;

        void DFS(int r, int c) {
            if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != originalColor) return;
            image[r][c] = newColor;
            DFS(r + 1, c);
            DFS(r - 1, c);
            DFS(r, c + 1);
            DFS(r, c - 1);
        }

        DFS(sr, sc);
        return image;
    }
}

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the image. In the worst-case scenario, we visit every pixel.
• Space Complexity: O(M * N) in the worst case due to the recursive call stack. In practice, it's often much less due to the early termination of recursive calls in many cases. If you use an iterative solution with a stack, the space complexity would be O(min(M,N)) in the worst case, representing the maximum depth of the stack. Using an in-place algorithm avoids the need for a separate visited array.