Problem Explanation

In this problem, you are given an image which is represented by a two-dimensional array of integers, with each integer representing the pixel value in the image ranging from 0 to 65535.

You are also given a starting pixel denoted by its row and column indices (sr, sc) and a new color value. You have to perform a "flood fill" on the image starting from the given pixel using the new color.

The flood fill operation involves replacing the starting pixel and all connected pixels of the same color with the new color. Here, a pixel is considered "connected" if it is adjacent to another pixel in the four cardinal directions (up, down, left, and right).

You have to continue the flood fill operation until there are no more connected pixels of the initial color. Once the flood fill operation is complete, you have to return the modified image.

Example Walkthrough

Consider the following example:

1
2
3image = [[1,1,1],[1,1,0],[1,0,1]]
4sr = 1, sc = 1, newColor = 2

Starting from the pixel at position (1, 1), which has the color '1', the flood fill operation changes the color of all connected pixels of color '1' to '2'. The output for this example would be:

1
2
3Output: [[2,2,2],[2,2,0],[2,0,1]]

Solution Approach

This problem can be solved using a depth-first search (DFS) approach. We start at the pixel identified by the coordinates (sr, sc), if the pixel color is same as the initial color, we change the pixel's color to the new color and then recursively perform the same operation for all its neighboring pixels.

If the pixel color is not the same as the initial color or if the pixel has already been visited, we return without making any changes. This ensures that only the pixels connected to the starting pixel and have the same color get changed.

Python Solution

1
2python
3class Solution(object):
4    def floodFill(self, image, sr, sc, newColor):
5        """
6        :type image: List[List[int]]
7        :type sr: int
8        :type sc: int
9        :type newColor: int
10        :rtype: List[List[int]]
11        """
12        R, C = len(image), len(image[0])
13        color = image[sr][sc]
14        if color == newColor: return image
15        def dfs(r, c):
16            if image[r][c] == color:
17                image[r][c] = newColor
18                for ni, nj in ((r-1, c), (r+1,c), (r,c-1), (r,c+1)):
19                    if 0 <= ni < R and 0 <= nj < C:
20                        dfs(ni, nj)
21
22        dfs(sr, sc)
23        return image

Java Solution

1
2java
3class Solution {
4    private int color;
5    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
6        color = image[sr][sc];
7        if (color != newColor) dfs(image, sr, sc, newColor);
8        return image;
9    }
10
11    private void dfs(int[][] image, int r, int c, int newColor) {
12        if (image[r][c] == color) {
13            image[r][c] = newColor;
14            if (r+1 < image.length) dfs(image, r+1, c, newColor);
15            if (r-1 >= 0) dfs(image, r-1, c, newColor);
16            if (c+1 < image[0].length) dfs(image, r, c+1, newColor);
17            if (c-1 >= 0) dfs(image, r, c-1, newColor);
18        }
19    }
20}

JavaScript Solution

1
2javascript
3var floodFill = function(image, sr, sc, newColor) {
4    const color = image[sr][sc];
5    if (color !== newColor) dfs(image, sr, sc, color, newColor);
6    return image;
7};
8
9function dfs(image, r, c, color, newColor) {
10    if (image[r][c] === color) {
11        image[r][c] = newColor;
12        if (r >= 1) dfs(image, r - 1, c, color, newColor);
13        if (c >= 1) dfs(image, r, c - 1, color, newColor);
14        if (r + 1 < image.length) dfs(image, r + 1, c, color, newColor);
15        if (c + 1 < image[0].length) dfs(image, r, c + 1, color, newColor);
16    }
17}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
6        if(image[sr][sc] == newColor) return image;
7        int rows = image.size(), cols = image[0].size();
8        int color = image[sr][sc];
9        dfs(image, sr, sc, newColor, color, rows, cols);
10        return image;
11    }
12    
13private:
14    void dfs(vector<vector<int>>& image, int sr, int sc, int newColor, int color, int rows, int cols) {
15        if(sr < 0 || sr >= rows || sc < 0 || sc >= cols || image[sr][sc] != color) return;
16        image[sr][sc] = newColor;
17        dfs(image, sr+1, sc, newColor, color, rows, cols);
18        dfs(image, sr-1, sc, newColor, color, rows, cols);
19        dfs(image, sr, sc+1, newColor, color, rows, cols);
20        dfs(image, sr, sc-1, newColor, color, rows, cols);
21    }
22};

C# Solution

1
2csharp
3public class Solution {
4    public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
5        if (image[sr][sc] == newColor) return image;
6        Fill(image, sr, sc, image[sr][sc], newColor);
7        return image;
8    }
9    
10    private void Fill(int[][] image, int i, int j, int color, int newColor) {
11        if (i < 0 || j < 0 || i >= image.Length || j >= image[i].Length || image[i][j] != color)
12            return;
13        image[i][j] = newColor;
14        Fill(image, i-1, j, color, newColor);
15        Fill(image, i+1, j, color, newColor);
16        Fill(image, i, j-1, color, newColor);
17        Fill(image, i, j+1, color, newColor);
18    }
19}

Explanation of Solutions

Python

The Python solution uses depth-first search (DFS) to flood fill the image. If the current color is not the same as the new color, recursion takes place. DFS is performed on the neighboring pixels if they are within the dimensions of the image and of the same color. After the DFS function has finished executing, the image is returned with the colors altered.

Java

The Java solution is similar to the Python solution. DFS is used to change all pixels of the original color to the new color. A private variable color keeps track of the original color and is compared with newColor as part of the base case for the DFS recursion. If a pixel's color is not the same as color, DFS doesn't perform any operation on the pixel.

JavaScript

The JavaScript implementation uses the same DFS approach. Here, color and newColor are arguments to the DFS function, and color is checked for each DFS recursive call to decide whether to change the color and continue the DFS from the current pixel.

C++

In the C++ solution, the DFS recursion is initiated only when the image at location (sr, sc) does not equal the newColor. In the DFS function, the color of the current pixel is changed only if it is within bounds and is of the same color as the original color.

C#

The C# solution has the same approach as the others with a slight variation. The Fill function is called only when the color at the starting pixel is not the same as the new color. If the pixel is out of bounds or not the same as the ‘color’, it will stop further DFS recursion. Upon passing these checks, the color of the pixel is changed to newColor and recursive calls are made for neighbors in all four directions.

These solutions demonstrate a classic DFS recursion for flood filling a two-dimensional matrix or image in different programming languages. They exhibit similarity in approach, tailoring DFS to match language syntax and style.