Problem: Flood Fill (Easy)

1. Problem Statement

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

2. The Mental Model: The "Paint Bucket" Intuition

Think of the "Paint Bucket" tool in Photoshop or MS Paint.

You click on a pixel.
The program checks: "What color is this?" (Let's call it oldColor).
It changes that pixel to the newColor.
It then "explores" all neighbors. If a neighbor is oldColor, it repeats the process.

This is a classic Connected Components problem on a grid. Because we want to explore as deep as possible before coming back, Depth-First Search (DFS) is the most natural fit.

3. Visual Execution (Propagation)

graph TD
    Start[Click (1,1)] --> N1[Check Up]
    Start --> N2[Check Down]
    Start --> N3[Check Left]
    Start --> N4[Check Right]
    
    subgraph "Recursive Step"
        N1 -- same color? --> Paint[Change to 2]
        Paint --> Recurse[Repeat for neighbors]
    end

4. Java Implementation (Recursive DFS)

public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int oldColor = image[sr][sc];
    
    // Safety Check: If the new color is the same as the old, do nothing
    // This prevents an infinite loop!
    if (oldColor != color) {
        dfs(image, sr, sc, oldColor, color);
    }
    
    return image;
}

private void dfs(int[][] image, int r, int c, int oldColor, int newColor) {
    // 1. Base Case: Out of bounds or not the target color
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] != oldColor) {
        return;
    }
    
    // 2. Action: Change the color
    image[r][c] = newColor;
    
    // 3. Recurse: Explore 4 neighbors
    dfs(image, r + 1, c, oldColor, newColor);
    dfs(image, r - 1, c, oldColor, newColor);
    dfs(image, r, c + 1, oldColor, newColor);
    dfs(image, r, c - 1, oldColor, newColor);
}

5. Verbal Interview Script (Staff Tier)

Interviewer: "What is the time complexity of this solution and can we avoid infinite loops?"

You: "The time complexity is $O(N)$ where $N$ is the total number of pixels in the grid, because in the worst case, we visit every pixel exactly once. Regarding infinite loops: a major trap in Flood Fill is when the newColor is the same as the oldColor. Without a check, the DFS would keep 're-painting' the same cell and recursing forever. I handle this by checking if (oldColor != newColor) at the start. Since we only visit cells of oldColor and change them to newColor, the state naturally progresses toward completion."

6. Staff-Level Follow-Ups

Follow-up 1: "Could we use BFS?"

The Answer: "Absolutely. A Breadth-First Search using a Queue would also solve this in $O(N)$ time. BFS would visit pixels in 'ripples' expanding out from the start, whereas DFS goes deep in one direction first. BFS is often safer for extremely large grids in languages with small stack limits, but for standard interview sizes, DFS is more concise."

Follow-up 2: "How would you handle an 8-directional fill?"

The Answer: "I would simply add 4 more recursive calls for the diagonals: (r+1, c+1), (r-1, c-1), (r+1, c-1), and (r-1, c+1). The core logic remains identical."

7. Performance Nuances (The Java Perspective)

Grid Boundaries: Always perform boundary checks (r < 0, etc.) before accessing the array image[r][c] to prevent ArrayIndexOutOfBoundsException.
Memory Locality: While we explore in 4 directions, rows in Java are stored contiguously. Accessing image[r][c+1] is slightly faster than image[r+1][c] because the latter jumps to a different row object on the heap. In extreme optimization scenarios, we might flatten the 2D grid into a 1D array.

6. Staff-Level Verbal Masterclass (Communication)

Interviewer: "How would you defend this specific implementation in a production review?"

You: "In a mission-critical environment, I prioritize the Big-O efficiency of the primary data path, but I also focus on the Predictability of the system. In this implementation, I chose a recursive approach with memoization. While a recursive solution is more readable, I would strictly monitor the stack depth. If this were to handle skewed inputs, I would immediately transition to an explicit stack on the heap to avoid a StackOverflowError. From a memory perspective, I leverage primitive arrays to ensure that we minimize the garbage collection pauses (Stop-the-world) that typically plague high-throughput Java applications."

7. Global Scale & Distributed Pivot

When a problem like this is moved from a single machine to a global distributed architecture, the constraints change fundamentally.

Data Partitioning: We would shard the input space using Consistent Hashing. This ensures that even if our dataset grows to petabytes, any single query only hits a small subset of our cluster, maintaining logarithmic lookup times.
State Consistency: For problems involving state updates (like DP or Caching), we would use a Distributed Consensus protocol like Raft or Paxos to ensure that all replicas agree on the final state, even in the event of a network partition (The P in CAP theorem).

8. Performance Nuances (The Staff Perspective)

Cache Locality: Accessing a 2D matrix in row-major order (reading [i][j] then [i][j+1]) is significantly faster than column-major order in modern CPUs due to L1/L2 cache pre-fetching. I always structure my loops to align with how the memory is physically laid out.
Autoboxing and Generics: In Java, using List<Integer> instead of int[] can be 3x slower due to the overhead of object headers and constant wrapping. For the most performance-sensitive sections of this algorithm, I advocate for primitive specialized structures.