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 also given three integers sr, sc, and newColor. You are given an image and a starting coordinate, sr, and sc. You should perform a flood fill on the image starting from the given coordinate and using newColor.

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 position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as the starting pixel are colored with the new color. Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

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. Define a recursive helper function: This function will recursively traverse the image, changing the color of connected pixels.
2. Base Cases:
   • Check if the current coordinates are out of bounds.
   • Check if the current pixel's color is different from the original color.
3. Recursive Step: If the current pixel's color matches the original color, change its color to newColor and recursively call the helper function on its four neighbors (up, down, left, right).
4. Initial Call: Call the helper function with the starting coordinates.
5. Return the modified image.

Explanation

The solution uses Depth-First Search (DFS) to traverse the connected component of pixels with the same color. The recursive helper function explores the image, changing the color of pixels only if they are within bounds, have the original color, and haven't been visited yet (implicitly handled by recursion). The base cases prevent infinite recursion and ensure that only connected pixels of the same original color are modified.

Code

function floodFill(image: number[][], sr: number, sc: number, newColor: number): number[][] {
    const originalColor = image[sr][sc];
    if (originalColor === newColor) return image; //No need to fill if colors are the same

    const rows = image.length;
    const cols = image[0].length;

    const dfs = (row: number, col: number) => {
        if (row < 0 || row >= rows || col < 0 || col >= cols || image[row][col] !== originalColor) {
            return;
        }
        image[row][col] = newColor;
        dfs(row + 1, col);
        dfs(row - 1, col);
        dfs(row, col + 1);
        dfs(row, col - 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, we might visit every pixel.
• Space Complexity: O(MN) in the worst case due to the recursive call stack. In the best case (a small connected component), it will be much less. An iterative approach using a stack would reduce the space complexity to O(MN) in the worst case, but in practice, the recursive approach often performs better because the function call overhead is typically smaller than the overhead of managing a stack explicitly.