Problem Description

The Flood Fill problem asks you to implement a function that takes in an image represented by a 2D grid of integers, where each integer represents the color of a pixel. You are also given the starting coordinates (sr, sc) (row and column) of a pixel and a newColor integer.

Your task is to replace the color of the starting pixel and all adjacent pixels (up, down, left, right) that have the same original color with newColor. This process repeats recursively for each pixel that is changed, effectively "filling" all connected pixels of the same color with the new color.

Key constraints:

• Only four-way (up, down, left, right) connectivity is considered—no diagonals.
• Do not change pixels that do not match the starting pixel's original color.
• If the starting pixel is already newColor, you can return the image as-is (to avoid infinite loops).
• There is only one valid output for a given input.

Thought Process

At first glance, this problem looks similar to a "paint bucket" tool in image editing software. The main challenge is to ensure that you only fill connected pixels of the same original color, and you don't accidentally revisit or overwrite pixels unnecessarily.

A brute-force approach might be to check every pixel in the image, but that's highly inefficient and doesn't respect the connectivity requirement. Instead, we need a way to start from the given pixel and expand outwards, only filling pixels that are directly connected and match the original color.

This naturally leads to thinking about graph traversal algorithms, such as Depth-First Search (DFS) or Breadth-First Search (BFS), since the image can be seen as a grid-based graph where each pixel is a node connected to its four neighbors.

The main optimization is to avoid unnecessary work by:

• Only visiting each pixel once.
• Stopping recursion or iteration when a pixel doesn't match the original color.
• Short-circuiting if the starting pixel's color is already the newColor.

Solution Approach

Here is a step-by-step guide to solving the Flood Fill problem:

1. Identify the original color: Store the color of the starting pixel. This is the color you want to replace.
2. Check for trivial case: If the original color is the same as newColor, return the image as-is. This avoids unnecessary work and infinite recursion.
3. Choose a traversal method: Use either DFS (recursive or stack-based) or BFS (queue-based) to explore all connected pixels of the original color.
4. Flood fill logic:
   • For each pixel, check if it's within bounds and if its color matches the original color.
   • If so, change its color to newColor.
   • Recursively (or iteratively) apply the same logic to its four neighbors (up, down, left, right).
5. Return the modified image: Once all connected pixels are filled, return the image.

We use DFS here because it's easy to implement recursively and naturally fits the problem's requirements. We keep track of visited pixels implicitly by changing their color to newColor.

Example Walkthrough

Let's consider the following example:

• image = [[1,1,1],[1,1,0],[1,0,1]]
• sr = 1, sc = 1
• newColor = 2

The starting pixel is at (1,1) with color 1. We want to fill all connected 1's with 2.

1. Start at (1,1): color is 1, change to 2.
2. Check up (0,1): color is 1, change to 2.
3. Check up (from 0,1 to -1,1): out of bounds, stop.
4. Check down (from 0,1 to 1,1): already 2, stop.
5. Check left (0,0): color is 1, change to 2.
6. Check right (0,2): color is 1, change to 2.
7. Continue recursively for all connected 1's.
8. Eventually, all connected 1's (except for (2,2)) are changed to 2.

Final image: [[2,2,2],[2,2,0],[2,0,1]]

Time and Space Complexity

Brute-force: If you checked every pixel regardless of connectivity, time complexity would be O(m*n), where m and n are the dimensions of the image.

Optimized (DFS/BFS): In the worst case, you might still visit every pixel (if all pixels are the same color), so time complexity is O(m*n). Each pixel is only visited once and changed at most once.

Space complexity:

• For recursive DFS, space is O(m*n) in the worst case due to the call stack (if the fill area is the entire image).
• For iterative BFS or DFS with a stack/queue, space is also O(m*n) in the worst case.

Code Implementation

class Solution:
    def floodFill(self, image, sr, sc, newColor):
        orig_color = image[sr][sc]
        if orig_color == newColor:
            return image

        def dfs(r, c):
            if (0 <= r < len(image) and 0 <= c < len(image[0]) and image[r][c] == orig_color):
                image[r][c] = newColor
                dfs(r+1, c)
                dfs(r-1, c)
                dfs(r, c+1)
                dfs(r, c-1)
        dfs(sr, sc)
        return image
      

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

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

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

Summary

The Flood Fill problem is a classic example of using graph traversal (DFS or BFS) to solve connectivity problems in grids. The key insight is to only fill connected pixels of the original color, and to avoid unnecessary work by checking for trivial cases. By using recursion or a stack/queue, you can efficiently fill all relevant pixels with the new color. The approach is simple, elegant, and leverages fundamental programming concepts.