DSA interview question

Flood Fill

Medium · Data structures · Topics: graph, dfs, bfs, matrix

The problem

A paint program's bucket tool recolours a region: starting from the clicked pixel, every pixel connected to it 4-directionally with the same original colour gets the new colour. It's a traversal (BFS or DFS) from the start pixel that only moves into neighbours with the original colour. One subtle case: if the new colour equals the original, nothing should change, and a naive implementation would loop forever, because recoloured pixels would still match.

Example: image [[1,1,1], [1,1,0], [1,0,1]], start (1, 1), colour 2 → [[2,2,2], [2,2,0], [2,0,1]].

Function signature

vector<vector<int>> floodFill(vector<vector<int>> image, int sr, int sc, int color);

Test cases

Input `(image, sr, sc, color)`	Output	Explanation
`([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)`	`[[2,2,2],[2,2,0],[2,0,1]]`	The bottom-right 1 touches only diagonally
`([[0,0,0],[0,1,0]], 1, 1, 2)`	`[[0,0,0],[0,2,0]]`	A single-pixel region
`([[1,2],[2,1]], 0, 0, 3)`	`[[3,2],[2,1]]`	Diagonals don't count
`([[0,0,0],[0,0,0]], 0, 0, 0)`	`[[0,0,0],[0,0,0]]`	Same colour: unchanged
`([[5]], 0, 0, 7)`	`[[7]]`

(Confirm: connectivity is 4-directional; only pixels of the starting pixel's original colour are recoloured.)

How interviewers phrase it

"Perform a flood fill on the image starting from pixel (sr, sc) with the new color" (LeetCode 733).

Clarifying questions to ask

4-directional or 8-directional? (4.)
Return a new image or modify in place? (Either; a copy is returned here.)
What if the new colour equals the old one? (Nothing changes.)

Follow-ups to expect

"Why is the same-colour case special?"
"BFS or DFS?"
"Why do you not need a visited array?"
"Where else is this pattern used?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview