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 should perform a flood fill on the image starting from the pixel image[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.

Given the image, the sr, sc, and newColor, return the modified image after performing the flood fill.

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 (with color 1) are colored with the new color (2). 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. Base Case: If the starting pixel's color is already equal to the newColor, no change is needed. Return the original image.

2. Recursive Helper Function: Create a recursive helper function dfs that takes the current row r, column c, the original color originalColor, and the image as input.

3. Bounds Check: Ensure that the current row r and column c are within the bounds of the image. If not, return.

4. Color Check: Check if the pixel at image[r][c] is equal to originalColor. If not, return (it's already a different color, or out of bounds).

5. Color Update: Update the color of the pixel image[r][c] to newColor.

6. Recursive Calls: Recursively call dfs for the four adjacent pixels (up, down, left, right).

7. Main Function: Call the helper function dfs with the initial row sr, column sc, the original color image[sr][sc], and the image.

8. Return: Return the modified image.

Explanation

The solution uses Depth-First Search (DFS) to traverse all connected pixels of the same color. The recursive helper function explores adjacent pixels, ensuring that only connected pixels with the original color are updated. The bounds check prevents accessing out-of-bounds array elements, ensuring the code handles edge cases correctly.

Code

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return image; // Base case: no change needed

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

        dfs(image, sr, sc, originalColor, newColor, rows, cols);
        return image;
    }

    private void dfs(int[][] image, int r, int c, int originalColor, int newColor, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != originalColor) return;

        image[r][c] = newColor;
        dfs(image, r + 1, c, originalColor, newColor, rows, cols); // Down
        dfs(image, r - 1, c, originalColor, newColor, rows, cols); // Up
        dfs(image, r, c + 1, originalColor, newColor, rows, cols); // Right
        dfs(image, r, c - 1, originalColor, newColor, rows, cols); // Left
    }
}

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(M*N) in the worst case due to the recursive call stack. The space complexity can be reduced to O(min(M,N)) by using an iterative approach with a stack instead of recursion.