Pseudo-code:

text
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.

Core Insight for Flood Fill

The efficient solution relies on the observation that the "flood" only moves from a pixel to its immediate neighbors. We do not need to scan the whole grid; we only need to explore the specific path of connections starting from (sr, sc).

The pattern Graph DFS allows us to explore this connected component deeply before backtracking. The key invariant maintained during traversal is that we only proceed to a node if it satisfies two conditions:

1. It is within the grid boundaries.
2. Its current color matches the originalColor.

By mutating the pixel's color to the newColor immediately upon visitation, we achieve two goals simultaneously:

1. We perform the required task (updating the image).
2. We mark the node as "visited." Since the color is now newColor (and assuming newColor != originalColor), subsequent checks will fail the second condition above, preventing infinite loops and redundant processing.

Visual Description: Imagine the execution as a recursion tree rooted at (sr, sc). When the algorithm processes a pixel, it changes its value and then "branches" out to the pixel's top, bottom, left, and right neighbors.

• If a neighbor is valid (same original color), it becomes a child node in the recursion tree, and the process repeats.
• If a neighbor is invalid (different color or out of bounds), that branch is pruned immediately (the recursive call returns).
• The recursion naturally terminates when all paths from the start node hit a boundary or a different color.

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.

Reference Implementation

C++ Solution for LeetCode 733

cpp
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        
        // If the color is already the target color, no change is needed.
        // This prevents infinite recursion.
        if (originalColor == color) {
            return image;
        }
        
        dfs(image, sr, sc, originalColor, color);
        return image;
    }
    
private:
    void dfs(vector<vector<int>>& image, int r, int c, int originalColor, int newColor) {
        // Check boundaries
        if (r < 0 || r >= image.size() || c < 0 || c >= image[0].size()) {
            return;
        }
        
        // If the current pixel is not the original color, stop.
        if (image[r][c] != originalColor) {
            return;
        }
        
        // Update the color
        image[r][c] = newColor;
        
        // Recurse in all 4 directions
        dfs(image, r + 1, c, originalColor, newColor);
        dfs(image, r - 1, c, originalColor, newColor);
        dfs(image, r, c + 1, originalColor, newColor);
        dfs(image, r, c - 1, originalColor, newColor);
    }
};

Java Solution for LeetCode 733

java
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        
        // Prevent infinite recursion if the start color is already the target color
        if (originalColor == color) {
            return image;
        }
        
        dfs(image, sr, sc, originalColor, color);
        return image;
    }
    
    private void dfs(int[][] image, int r, int c, int originalColor, int newColor) {
        // Boundary checks
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) {
            return;
        }
        
        // If the pixel does not match the original color, it's not part of the component
        if (image[r][c] != originalColor) {
            return;
        }
        
        // Update the pixel color
        image[r][c] = newColor;
        
        // Recurse to neighbors
        dfs(image, r + 1, c, originalColor, newColor);
        dfs(image, r - 1, c, originalColor, newColor);
        dfs(image, r, c + 1, originalColor, newColor);
        dfs(image, r, c - 1, originalColor, newColor);
    }
}

Python Solution for LeetCode 733

python
class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original_color = image[sr][sc]
        rows, cols = len(image), len(image[0])
        
        # If the start pixel is already the target color, return immediately
        if original_color == color:
            return image
            
        def dfs(r, c):
            # Check boundaries
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            
            # If pixel is not the original color, stop traversal
            if image[r][c] != original_color:
                return
            
            # Update color
            image[r][c] = color
            
            # Recurse 4-directionally
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        
        dfs(sr, sc)
        return image

Q: Why is my solution TLE (Time Limit Exceeded)? A: You might be re-visiting nodes. In graph traversal, you must mark nodes as visited. In this problem, changing the color serves as the "visited" marker. If you check the color after the recursive call instead of before, or if you don't update the color before recursing, you will process the same nodes exponentially many times.