Flood Fill

Flood Fill

1. What is this problem about?

The Flood Fill interview question simulates the "bucket fill" tool in image editors. You are given a grid, a starting pixel $(sr, sc)$, and a newColor. You need to change the color of the starting pixel and all adjacent pixels (up, down, left, right) that share the same initial color. This process continues recursively for the newly colored pixels.

2. Why is this asked in interviews?

This is a standard question at Apple, Meta, and Microsoft. It tests your knowledge of Graph Traversal algorithms—specifically Breadth-First Search (BFS) or Depth-First Search (DFS). It evaluations whether you can handle connectivity in a grid and correctly manage a "visited" state to avoid infinite loops. It's a core Matrix interview pattern.

3. Algorithmic pattern used

This problem is typically solved using DFS or BFS.

1. Base Case: If the starting pixel already has the newColor, return the image immediately (to prevent infinite recursion).
2. Recursive Step (DFS):
   • Store the original color.
   • Change the current pixel's color to newColor.
   • Recursively call the function for all 4 neighbors IF they have the original color.
3. Queue Step (BFS): Push $(sr, sc)$ to a queue and process neighbors level-by-level.

4. Example explanation

Grid:

1 1 1
1 1 0
1 0 1

Start at (1, 1), Color 1, New Color 2.

1. (1, 1) changes to 2.
2. Check neighbors: (0, 1), (1, 0), (1, 2), (2, 1).
3. (0, 1) and (1, 0) are color 1. They change to 2 and trigger their own neighbor checks.
4. (1, 2) is color 0. Ignore.
5. The "lake" of 1s connected to the start becomes a lake of 2s.

5. Common mistakes candidates make

• Infinite Recursion: Forgetting the check if (oldColor == newColor) which causes the code to keep "filling" pixels that are already the correct color.
• Diagonal checks: Including diagonal neighbors when the problem usually specifies only 4-directional connectivity.
• Boundary checks: Failing to check if coordinates are within the grid dimensions before accessing the array.

6. Interview preparation tip

Master both BFS and DFS for grid traversals. DFS is often shorter to write recursively, but BFS is safer for very large grids where stack depth might be an issue. Mentioning this trade-off shows seniority in Graph interview patterns.