Flood Fill

EasyGraphsdfs grid

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a 2D grid image where image[r][c] is an integer representing the color of the pixel at row r and column c. You are also given a starting pixel located at coordinates (sr, sc) and a new color value color. Perform a *flood fill* starting from the pixel (sr, sc): 1. Begin at the starting pixel and remember its original color. 2. Recolor the starting pixel with color. 3. Spread to any pixel that is *4-directionally adjacent* (up, down, left, right) to an already-recolored pixel **and** shares the same original color as the starting pixel. Recolor each such pixel with color. 4. Continue spreading until no more reachable same-colored pixels remain. Return the grid after the fill is complete. Note: pixels are only connected horizontally and vertically, never diagonally. Also be careful with the case where the starting pixel already holds the target color — filling must still terminate.

Examples

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]]
Starting from the center pixel (color 1), every pixel reachable through 4-directional moves while staying on color-1 pixels is recolored to 2. The pixel at the bottom-right corner is also color 1 but is cut off by the 0s, so it stays 1.
Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 5
Output: [[5,5,5],[5,5,5]]
The entire grid is one connected region of color 0, so all pixels become 5.
Input: image = [[0,0,0],[0,1,0]], sr = 1, sc = 1, color = 1
Output: [[0,0,0],[0,1,0]]
The starting pixel already has color 1, so the grid is unchanged. The algorithm must avoid looping forever in this situation.

Constraints

  • `m == image.length`
  • `n == image[i].length`
  • `1 <= m, n <= 50`
  • `0 <= image[i][j], color < 2^16`
  • `0 <= sr < m`
  • `0 <= sc < n`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs grid problems