Flood Fill easy

Problem Statement

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value at the coordinate (i, j).

You are given an integer array sr and sc as the starting coordinates of a pixel that has a color color. You also have a target color newColor.

You should perform a flood fill on the image starting from the given coordinates. That means that every pixel connected to the pixel at (sr, sc) (directly or indirectly) that has color color should be changed to newColor. If it is a boundary point that is outside the grid, you will not paint this pixel.

The function should 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, color = 2, newColor = 2

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

Explanation: From the center of the image (sr=1, sc=1), all connected 1s are changed to 2. Note that only the 1s connected to (1,1) are changed.

Example 2

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

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

Explanation: Since the starting coordinate's color is already 0, there's no need to change anything. But all connected 0s should be changed to 2.

Steps

1. Base Case: If the starting coordinates are out of bounds, or the starting pixel's color is already equal to the newColor, return the image.

2. Recursive Step:

   • Change the color of the current pixel image[sr][sc] to newColor.
   • Recursively call the function for its adjacent pixels (up, down, left, right) if they are within the bounds of the image and have the original color.

3. Return: Return the modified image.

Explanation

The solution uses Depth-First Search (DFS) to traverse the connected component of pixels with the original color. The recursion explores all connected pixels efficiently. The base cases prevent infinite recursion and ensure that only pixels with the original color are changed. The order in which the neighbors are checked doesn't affect the final result, as all connected components will be visited.

Code

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color, int newColor) {
        int m = image.size();
        int n = image[0].size();
        int originalColor = image[sr][sc];

        if (sr < 0 || sr >= m || sc < 0 || sc >= n || image[sr][sc] == newColor) {
            return image;
        }

        image[sr][sc] = newColor;

        floodFill(image, sr + 1, sc, originalColor, newColor); // Down
        floodFill(image, sr - 1, sc, originalColor, newColor); // Up
        floodFill(image, sr, sc + 1, originalColor, newColor); // Right
        floodFill(image, sr, sc - 1, originalColor, newColor); // Left

        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(M*N) in the worst-case scenario due to the recursive call stack. In the best case, if the starting pixel already has the newColor, the space complexity is O(1). However, the recursive call stack could potentially reach a depth proportional to the size of the image. An iterative approach using a stack would reduce space complexity to O(M) or O(N), depending on the shape of the connected component.