733. Flood Fill

Problem Description

An image is represented by an m x n integer grid 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), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

Examples:

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) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) 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.

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

Constraints:

• m == image.length
• n == image[i].length
• 1 ≤ m, n ≤ 50
• 0 ≤ image[i][j], newColor < 2^16
• 0 ≤ sr < m
• 0 ≤ sc < n

Python Solution

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        if not image or image[sr][sc] == newColor:
            return image
            
        def dfs(r: int, c: int, oldColor: int):
            if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]) or image[r][c] != oldColor:
                return
                
            image[r][c] = newColor
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                dfs(r + dr, c + dc, oldColor)
        
        dfs(sr, sc, image[sr][sc])
        return image

Implementation Notes:

• Uses depth-first search to traverse connected pixels
• Time complexity: O(m × n) where m and n are the dimensions of the image
• Space complexity: O(m × n) for the recursion stack in worst case

Java Solution

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image == null || image.length == 0 || image[sr][sc] == newColor) {
            return image;
        }
        
        dfs(image, sr, sc, image[sr][sc], newColor);
        return image;
    }
    
    private void dfs(int[][] image, int r, int c, int oldColor, int newColor) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] != oldColor) {
            return;
        }
        
        image[r][c] = newColor;
        dfs(image, r + 1, c, oldColor, newColor);
        dfs(image, r - 1, c, oldColor, newColor);
        dfs(image, r, c + 1, oldColor, newColor);
        dfs(image, r, c - 1, oldColor, newColor);
    }
}

C++ Solution

class Solution {
private:
    void dfs(vector>& image, int r, int c, int oldColor, int newColor) {
        if (r < 0 || r >= image.size() || c < 0 || c >= image[0].size() || image[r][c] != oldColor) {
            return;
        }
        
        image[r][c] = newColor;
        dfs(image, r + 1, c, oldColor, newColor);
        dfs(image, r - 1, c, oldColor, newColor);
        dfs(image, r, c + 1, oldColor, newColor);
        dfs(image, r, c - 1, oldColor, newColor);
    }
    
public:
    vector> floodFill(vector>& image, int sr, int sc, int newColor) {
        if (image.empty() || image[sr][sc] == newColor) {
            return image;
        }
        
        dfs(image, sr, sc, image[sr][sc], newColor);
        return image;
    }
};

JavaScript Solution

function floodFill(image, sr, sc, newColor) {
    if (!image || image[sr][sc] === newColor) {
        return image;
    }
    
    function dfs(r, c, oldColor) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== oldColor) {
            return;
        }
        
        image[r][c] = newColor;
        dfs(r + 1, c, oldColor);
        dfs(r - 1, c, oldColor);
        dfs(r, c + 1, oldColor);
        dfs(r, c - 1, oldColor);
    }
    
    dfs(sr, sc, image[sr][sc]);
    return image;
}

C# Solution

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
        if (image == null || image.Length == 0 || image[sr][sc] == newColor) {
            return image;
        }
        
        DFS(image, sr, sc, image[sr][sc], newColor);
        return image;
    }
    
    private void DFS(int[][] image, int r, int c, int oldColor, int newColor) {
        if (r < 0 || r >= image.Length || c < 0 || c >= image[0].Length || image[r][c] != oldColor) {
            return;
        }
        
        image[r][c] = newColor;
        DFS(image, r + 1, c, oldColor, newColor);
        DFS(image, r - 1, c, oldColor, newColor);
        DFS(image, r, c + 1, oldColor, newColor);
        DFS(image, r, c - 1, oldColor, newColor);
    }
}

Implementation Notes:

• Uses depth-first search to traverse connected pixels
• Time complexity: O(m × n) where m and n are the dimensions of the image
• Space complexity: O(m × n) for the recursion stack in worst case