1. Understanding the Problem

You are given a 2D array (matrix) called image, where each integer represents the color of a pixel. You are also given a starting coordinate (sr, sc) (starting row, starting column), and a color (the new color).

Your task is to perform a "flood fill" on the image starting from the given pixel, and return the modified image.

What is a Flood Fill?

To perform a flood fill, you change the color of the starting pixel to the new color. Then, you look at its immediate neighbors (up, down, left, right). If those neighbors have the same original color as the starting pixel, you change their color too. You repeat this process outward until you hit boundaries or pixels of a different color.

The Core Constraint (The Edge Case):

If the starting pixel is already the new color, you do not need to do anything. In fact, if you don't handle this edge case, your code might get trapped in an infinite loop!

2. The Core Intuition: The Paint Bucket Tool

If you have ever used Microsoft Paint or Photoshop, you already intuitively understand this problem. When you select the "Paint Bucket" tool and click on a white background with red paint, the red paint spreads in all four directions until it hits a black border or the edge of the canvas.

In computer science, this spreading behavior is classically modeled using Depth-First Search (DFS) or Breadth-First Search (BFS). For this guide, we will use DFS because it is incredibly clean and intuitive to write recursively. We will stand on our current pixel, paint it, and then recursively call our paint function on the four pixels immediately surrounding it.

3. The Logic Step-by-Step

1. Identify the Target Color: Look at the starting pixel image[sr][sc] and store its current color. This is the original_color we want to replace.
2. The Edge Case Check: If the original_color is exactly the same as the new color, return the image immediately. There is no work to be done!
3. Define the Recursive DFS Function: Create a helper function that takes a row and a column as arguments.
   • The Boundary Check (Base Case): If the current row or column is out of bounds (less than 0, or greater than the matrix dimensions), stop and return.
   • The Color Check: If the current pixel's color does not match the original_color, stop and return.
   • The Action: Change the current pixel to the new color.
   • The Spreading: Recursively call the DFS function for the pixel above, below, to the left, and to the right.
4. Trigger the DFS: Call your recursive function on the starting coordinates (sr, sc).
5. Return: Once the recursion finishes spreading, return the updated image.

4. Complexity Analysis

• Time Complexity: O(M × N) — Where M is the number of rows and N is the number of columns. In the worst-case scenario (e.g., the entire image is a single solid color), we will visit and update every single pixel exactly once.
• Space Complexity: O(M × N) — This is the space used by the recursive call stack. If the entire image needs to be painted, the recursion goes M × N levels deep before unwinding.

5. Code Implementations

Expand the sections below to see the optimal DFS implementations across different languages.

class Solution:
    def floodFill(self, image, sr, sc, color):
        original_color = image[sr][sc]
        
        # Edge case: If the color is already the new color, do nothing
        if original_color == color:
            return image
            
        rows = len(image)
        cols = len(image[0])
        
        def dfs(r, c):
            # 1. Check if out of bounds
            # 2. Check if the pixel is NOT the color we want to change
            if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != original_color:
                return
                
            # Paint the current pixel
            image[r][c] = color
            
            # Recursively explore all 4 directions
            dfs(r + 1, c) # Down
            dfs(r - 1, c) # Up
            dfs(r, c + 1) # Right
            dfs(r, c - 1) # Left
            
        # Start the flood fill from the given coordinates
        dfs(sr, sc)
        
        return image

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        
        // Edge case: If the start pixel is already the target color, return
        if (originalColor != color) {
            dfs(image, sr, sc, originalColor, color);
        }
        
        return image;
    }
    
    private void dfs(int[][] image, int r, int c, int originalColor, int newColor) {
        // Check boundaries and if the current pixel is the original color
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] != originalColor) {
            return;
        }
        
        // Paint the current pixel
        image[r][c] = newColor;
        
        // Spread in 4 directions
        dfs(image, r + 1, c, originalColor, newColor); // Down
        dfs(image, r - 1, c, originalColor, newColor); // Up
        dfs(image, r, c + 1, originalColor, newColor); // Right
        dfs(image, r, c - 1, originalColor, newColor); // Left
    }
}

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        
        if (originalColor != color) {
            dfs(image, sr, sc, originalColor, color);
        }
        
        return image;
    }
    
private:
    void dfs(std::vector<std::vector<int>>& image, int r, int c, int originalColor, int newColor) {
        // Check boundaries and color mismatch
        if (r < 0 || r >= image.size() || c < 0 || c >= image[0].size() || image[r][c] != originalColor) {
            return;
        }
        
        // Paint the current pixel
        image[r][c] = newColor;
        
        // Spread in 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);
    }
};

6. Conclusion: You Are Ready

Congratulations, you have just implemented your first 2D matrix Depth-First Search! "Flood Fill" is a fantastic foundational problem because it forces you to think about boundary conditions (staying inside the grid) and base cases (preventing infinite recursion). The exact same DFS pattern you just learned here is used to solve much harder interview questions like "Number of Islands" and "Word Search". Keep this grid-traversal template in your toolkit, and you will dominate graph problems in your upcoming interviews.