Flood Fill

LeetCode 733: Flood Fill Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses Depth-First Search (DFS) to traverse and update the connected component of pixels matching the starting color.

The problem requires modifying a specific region of a 2D grid representing an image. Given a starting pixel (sr, sc) and a target color, we must change the color of the starting pixel and all 4-directionally connected pixels that share the same initial color. This process repeats recursively for the neighbors of the updated pixels. This is a classic implementation of the Flood Fill algorithm, a popular interview question often found in computer graphics applications.

LeetCode 733 asks us to return the modified grid after all reachable pixels of the original color have been updated to the new color.

Brute Force Approach for Flood Fill

A naive approach to solving the Flood Fill problem involves iteratively scanning the entire grid to propagate the color change. Instead of following the connections directly, one might attempt to sweep through the matrix repeatedly.

Naive Algorithm:

1. Identify the originalColor at (sr, sc).
2. Change image[sr][sc] to the newColor.
3. Loop repeatedly:
   • Iterate through every pixel (i, j) in the grid.
   • If image[i][j] is the newColor, check its 4 neighbors.
   • If a neighbor has the originalColor, change it to the newColor and mark a flag indicating a change occurred.
4. Stop looping when a full pass over the grid results in no changes.

Pseudo-code:

changed = true
while changed is true:
    changed = false
    for r from 0 to m-1:
        for c from 0 to n-1:
            if image[r][c] == newColor:
                for neighbor in getNeighbors(r, c):
                    if image[neighbor] == originalColor:
                        image[neighbor] = newColor
                        changed = true

Complexity Analysis:

• Time Complexity: $O((M \times N)^2)$. In the worst-case scenario (e.g., a snake-like path of pixels), the color propagates one step per full grid scan. Since there are $M \times N$ pixels, we might perform $M \times N$ passes, each taking $O(M \times N)$ time.
• Space Complexity: $O(1)$ auxiliary space (excluding input), as it modifies the grid in place without recursion or queues.

Why it fails: While this approach works for very small constraints, it is highly inefficient. The time complexity is quadratic relative to the total number of pixels. For larger grids, this results in a Time Limit Exceeded (TLE). It fails to utilize the structural property of the graph (adjacency), performing redundant checks on pixels that are not part of the active boundary.

Algorithm Strategy: Graph DFS

We will implement a Depth-First Search to traverse the connected component.

1. Initialization:

   • First, retrieve the originalColor from image[sr][sc].
   • Critical Check: If originalColor is already equal to color (the new color), no work is needed. Returning the original image immediately is crucial to avoid infinite recursion (as the "visited" logic relies on the color changing).

2. DFS Function:

   • Define a recursive function dfs(row, col) that takes the current coordinates.
   • Base Case (Pruning): Check if row or col are out of grid bounds, or if image[row][col] does not match originalColor. If any of these are true, return immediately.
   • Process Node: Update image[row][col] to color.
   • Recursive Step: Call dfs for all four adjacent coordinates: (row-1, col), (row+1, col), (row, col-1), and (row, col+1).

3. Invocation:

   • Call the dfs function starting at (sr, sc).
   • Return the modified image.

This strategy ensures every reachable pixel of the correct color is visited exactly once.

Execution Flow

Let's trace the algorithm with image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2. originalColor is 1. newColor is 2.

1. Start: Call dfs(1, 1).
2. Step 1 (Visit 1,1):
   • image[1][1] is 1 (matches original).
   • Update image[1][1] to 2. Grid is now [[1,1,1],[1,2,0],[1,0,1]].
   • Recurse Up: dfs(0, 1).
3. Step 2 (Visit 0,1):
   • image[0][1] is 1.
   • Update image[0][1] to 2.
   • Recurse Up: dfs(-1, 1) -> Out of bounds, return.
   • Recurse Down: dfs(1, 1) -> Value is 2 (not original 1), return.
   • Recurse Left: dfs(0, 0).
4. Step 3 (Visit 0,0):
   • image[0][0] is 1.
   • Update image[0][0] to 2.
   • Recurse neighbors... (process continues).
5. Step 4 (Backtracking):
   • Once dfs(0, 0) finishes its neighbors, it returns control to dfs(0, 1).
   • dfs(0, 1) continues to its next neighbor (Right: dfs(0, 2)).
6. Termination:
   • The process continues until all 1s connected to (1, 1) are turned to 2.
   • The bottom-right 1 at (2, 2) is never visited because it is separated by 0s.

Proof of Correctness

The correctness of this DFS approach relies on the connectivity property of the graph.

• Completeness: The algorithm explores all 4 directions from every visited node. By induction, if a node is reachable via a path of originalColor pixels, the DFS will eventually reach it.
• Termination: The algorithm changes the color of a visited node from originalColor to newColor. Since we only recurse on nodes with originalColor, a node cannot be visited twice (assuming originalColor != newColor). The number of pixels is finite ($M \times N$), so the recursion must terminate.

Pattern Reuse Notes

The Graph DFS - Connected Components pattern used in LeetCode 733 is fundamental for many matrix problems.

• LeetCode 200: Number of Islands: Instead of changing a color, you iterate through the grid, and for every "land" cell found, you trigger a DFS to mark the entire island as visited.
• LeetCode 130: Surrounded Regions: Uses DFS starting from the boundary of the grid to identify regions that cannot be captured.
• LeetCode 417: Pacific Atlantic Water Flow: Runs DFS from the ocean borders inward to find cells that can flow to the oceans.
• LeetCode 547: Number of Provinces: Applies the same connected components logic, but on an adjacency matrix representing cities rather than a pixel grid.

Reference Implementation

C++ Solution for LeetCode 733

1class Solution {
2public:
3    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
4        int originalColor = image[sr][sc];
5        
6        // If the color is already the target color, no change is needed.
7        // This prevents infinite recursion.
8        if (originalColor == color) {
9            return image;
10        }
11        
12        dfs(image, sr, sc, originalColor, color);
13        return image;
14    }
15    
16private:
17    void dfs(vector<vector<int>>& image, int r, int c, int originalColor, int newColor) {
18        // Check boundaries
19        if (r < 0 || r >= image.size() || c < 0 || c >= image[0].size()) {
20            return;
21        }
22        
23        // If the current pixel is not the original color, stop.
24        if (image[r][c] != originalColor) {
25            return;
26        }
27        
28        // Update the color
29        image[r][c] = newColor;
30        
31        // Recurse in all 4 directions
32        dfs(image, r + 1, c, originalColor, newColor);
33        dfs(image, r - 1, c, originalColor, newColor);
34        dfs(image, r, c + 1, originalColor, newColor);
35        dfs(image, r, c - 1, originalColor, newColor);
36    }
37};

Java Solution for LeetCode 733

1class Solution {
2    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
3        int originalColor = image[sr][sc];
4        
5        // Prevent infinite recursion if the start color is already the target color
6        if (originalColor == color) {
7            return image;
8        }
9        
10        dfs(image, sr, sc, originalColor, color);
11        return image;
12    }
13    
14    private void dfs(int[][] image, int r, int c, int originalColor, int newColor) {
15        // Boundary checks
16        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) {
17            return;
18        }
19        
20        // If the pixel does not match the original color, it's not part of the component
21        if (image[r][c] != originalColor) {
22            return;
23        }
24        
25        // Update the pixel color
26        image[r][c] = newColor;
27        
28        // Recurse to neighbors
29        dfs(image, r + 1, c, originalColor, newColor);
30        dfs(image, r - 1, c, originalColor, newColor);
31        dfs(image, r, c + 1, originalColor, newColor);
32        dfs(image, r, c - 1, originalColor, newColor);
33    }
34}

Python Solution for LeetCode 733

1class Solution:
2    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
3        original_color = image[sr][sc]
4        rows, cols = len(image), len(image[0])
5        
6        # If the start pixel is already the target color, return immediately
7        if original_color == color:
8            return image
9            
10        def dfs(r, c):
11            # Check boundaries
12            if r < 0 or r >= rows or c < 0 or c >= cols:
13                return
14            
15            # If pixel is not the original color, stop traversal
16            if image[r][c] != original_color:
17                return
18            
19            # Update color
20            image[r][c] = color
21            
22            # Recurse 4-directionally
23            dfs(r + 1, c)
24            dfs(r - 1, c)
25            dfs(r, c + 1)
26            dfs(r, c - 1)
27        
28        dfs(sr, sc)
29        return image