G-9. Flood Fill Algorithm

The Flood Fill algorithm is a classic graph traversal problem that determines and re-colors a connected component of pixels in a 2D grid. Given a starting pixel coordinate (sr, sc) and a newColor, the objective is to replace the color of the starting pixel, along with any pixels connected four-directionally (up, down, left, right) of the same initial color, recursively propagating outward until all connected matching pixels are updated.

1. Problem Statement & Core Objective

Imagine an image represented as a 2D grid (matrix) of integers where each integer represents a pixel value.

Input: A 2D matrix (image), a starting row (sr), a starting column (sc), and a newColor.
Four-Directional Connectivity: A pixel is connected to another if they share an edge (top, bottom, left, or right). Diagonal connectivity is not allowed in standard flood fill.
Rule of Propagation: Starting from image[sr][sc] (let's call its value initialColor), we change its color to newColor. Then, we check its 4-directional neighbors. If a neighbor has the exact same initialColor and has not yet been converted, we transition to it, change its color, and repeat the process recursively.

2. Real-Life Analogy: The Paint Bucket Tool

Real-Life Analogy: Think of the Paint Bucket (Flood Fill) tool in graphic design software like Microsoft Paint or Photoshop. When you click on a specific region of a digital drawing with a bucket of blue paint, the tool inspects the color of the pixel you clicked. It then spills outward, bleeding into every adjacent pixel of that same exact color, stopping only when it hits a boundary of a different color or the edge of the image canvas.

3. Step-by-Step Evolution: Visualizing the Matrix Walkthrough

Let us trace a concrete matrix example to understand how the propagation works.

Example Configuration:

Suppose we have a 3x3 matrix where the numbers represent pixel colors:

CODE

[1, 1, 1]
[1, 1, 0]
[1, 0, 1]

Starting Coordinate: sr = 0, sc = 0 (Top-left corner, value = 1)
Initial Color: 1
New Color: 2

Propagation Steps:

Initial Click: We check image[0][0], which is 1. We record initialColor = 1 and update this cell to 2.
First-Level Neighbors: From (0,0), we look at its 4-directional neighbors:
- Right (0,1): Value is 1 (Matches initialColor). Update to 2.
- Down (1,0): Value is 1 (Matches initialColor). Update to 2.
- Up / Left: Out of bounds.
Second-Level Neighbors:
- From (0,1), its right neighbor (0,2) is 1 -> Update to 2. Its down neighbor (1,1) is 1 -> Update to 2.
- From (1,0), its down neighbor (2,0) is 1 -> Update to 2.
Final Configuration:
CODE
```
[2, 2, 2]
[2, 2, 0]
[2, 0, 1]
```
Notice that the 0 at (1,2) and (2,1) and the 1 at (2,2) are not touched because they are either not connected, blocked by a different color boundary, or do not match the initialColor at the moment of expansion.

4. Software Engineering Best Practice: Avoid Tampering with Input Data

When designing algorithms in a professional software engineering environment, adhering to clean data handling principles is critical:

Rule of Immutable Input: Never tamper with or mutate raw input data structures unless explicitly instructed or optimized for space-constrained embedded systems. Data passed into a function should be treated as read-only.
The Solution: Create a clean copy of the input matrix (let's call it ans) and perform all color mutations, visits, and flood operations on this copied matrix, returning the copy at the end.

5. Algorithmic Choice: BFS vs. DFS

Both Breadth-First Search (BFS) and Depth-First Search (DFS) can solve this problem because the ultimate requirement is simply to find and color all connected components rather than finding a shortest path.

BFS explores level by level using a Queue.
DFS dives deep along a single path until it hits a dead end or an already visited/colored node, then backtracks. In this chapter, we implement DFS via recursion to explore the depth of the connected grid components.

6. Navigating 4-Directional Neighbors Using Delta Arrays

To avoid writing four separate conditional blocks for visiting the top, right, bottom, and left neighbors, we use Delta Arrays (delRow and delCol). This technique simplifies coordinate math.

Structure & Concept Flow

Direction | delRow | delCol | Resulting Movement

--------------+--------+--------+-------------------

Top | -1 | 0 | Row - 1, Col

Right | 0 | +1 | Row, Col + 1

Bottom | +1 | 0 | Row + 1, Col

Left | 0 | -1 | Row, Col - 1

Delta Arrays Declaration:

int delRow[] = {-1, 0, +1, 0};
int delCol[] = {0, +1, 0, -1};

For any given cell (row, col), its four neighbors can be computed in a loop:

C++

int nRow = row + delRow[i];
int nCol = col + delCol[i];

7. Complete Code Implementation (C++ & Java)

C++ Implementation

C++

class Solution {
private:
    void dfs(int row, int col, vector<vector<int>>& ans, 
             vector<vector<int>>& image, int newColor, 
             int iniColor, int delRow[], int delCol[]) {
        
        // Color the current pixel in the answer matrix
        ans[row][col] = newColor;
        int n = image.size();
        int m = image[0].size();
        
        // Traverse all 4 neighbors
        for (int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            
            // Check validity: within bounds, matches initial color, and not yet recolored
            if (nRow >= 0 && nRow < n && nCol >= 0 && nCol < m && 
                image[nRow][nCol] == iniColor && ans[nRow][nCol] != newColor) {
                dfs(nRow, nCol, ans, image, newColor, iniColor, delRow, delCol);
            }
        }
    }

public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int iniColor = image[sr][sc];
        vector<vector<int>> ans = image; // Copy input matrix to prevent mutation
        
        int delRow[] = {-1, 0, +1, 0};
        int delCol[] = {0, +1, 0, -1};
        
        dfs(sr, sc, ans, image, newColor, iniColor, delRow, delCol);
        return ans;
    }
};

Java Implementation

JAVA

class Solution {
    private void dfs(int row, int col, int[][] ans, int[][] image, 
                     int newColor, int iniColor, int[] delRow, int[] delCol) {
        
        // Color the current pixel in the answer matrix
        ans[row][col] = newColor;
        int n = image.length;
        int m = image[0].length;
        
        // Traverse all 4 neighbors
        for (int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            
            // Check validity: within bounds, matches initial color, and not yet recolored
            if (nRow >= 0 && nRow < n && nCol >= 0 && nCol < m && 
                image[nRow][nCol] == iniColor && ans[nRow][nCol] != newColor) {
                dfs(nRow, nCol, ans, image, newColor, iniColor, delRow, delCol);
            }
        }
    }

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int iniColor = image[sr][sc];
        
        // Create a deep copy of the image matrix
        int[][] ans = new int[image.length][image[0].length];
        for (int i = 0; i < image.length; i++) {
            for (int j = 0; j < image[0].length; j++) {
                ans[i][j] = image[i][j];
            }
        }
        
        int[] delRow = {-1, 0, +1, 0};
        int[] delCol = {0, +1, 0, -1};
        
        dfs(sr, sc, ans, image, newColor, iniColor, delRow, delCol);
        return ans;
    }
}

8. Complexity Analysis

Complexity Type	Analysis	Explanation
Time Complexity	$O(N \times M)$	In the worst-case scenario (e.g., every single pixel in the grid has the identical color), every node in the $N \times M$ matrix is visited once, with 4 constant neighbor checks per node.
Space Complexity	$O(N \times M)$	Dominated by two factors: <br>1. Answer Matrix Storage: $O(N \times M)$ space used to store the copied grid.<br>2. Recursive Stack Space: In the worst-case scenario where all pixels form a single linear or complex path, the recursion stack can grow up to $O(N \times M)$ depth.

Summary and Key Takeaways

Problem Core: Flood fill is a connected-component traversal problem on a 2D matrix, mimicking paint bucket tools in image editors.
Connectivity: Restricted strictly to 4 directions (Up, Down, Left, Right) using delta coordinate arrays.
Data Integrity: Best software engineering practice dictates copying the input matrix into a separate answer array rather than mutating original source data.
Traversal Strategy: Both BFS and DFS work seamlessly; DFS dives deep recursively along matching color paths, while BFS explores outward layer by layer.
Infinite Loop Prevention: Checking whether a neighbor has already been assigned the newColor (ans[nRow][nCol] != newColor) prevents redundant recursive loops and stack overflows.
Time Complexity: $O(N \times M)$ to visit every cell in the grid.
Space Complexity: $O(N \times M)$ accounting for the copied result matrix and maximum recursive stack depth.