Flood fill: recolor a connected region of an image

An image is a grid of integer colors. Given a starting pixel (sr, sc) and a new_color, recolor the starting pixel and every pixel connected to it through up, down, left or right moves that has the same original color. Write it once with breadth-first search and once with depth-first search.

Interface

Unless you agree on a different interface with the interviewer, assume:

• flood_fill(image: list[list[int]], sr: int, sc: int, new_color: int) -> list[list[int]]: returns the recolored image.

Example

image = [[1, 1, 0],
         [1, 0, 1],
         [0, 1, 1]]
flood_fill(image, 0, 0, 2)  ->  [[2, 2, 0],
                                 [2, 0, 1],
                                 [0, 1, 1]]     # the 1s at the bottom right aren't connected
flood_fill(image, 0, 0, 1)  ->  unchanged       # new color equals the old one

Constraints

• Up to 50 by 50 pixels in the base version; colors are small non-negative integers.
• Diagonal pixels are not connected.

Clarifying questions

• Should I change the image in place or return a copy?
• What if the new color equals the original color?
• How large can the image get? (Recursion depth matters for DFS.)

What a strong answer covers

• BFS with a queue and DFS with recursion or an explicit stack, both O(rows × cols).
• Marking a pixel when it is enqueued, not when it is dequeued, so nothing is added twice.
• Returning early when the new color equals the old one, which otherwise loops forever.
• Why recursive DFS can overflow the stack on a large image, and the iterative fix.

Follow-ups

• Fill with 8-way connectivity.
• The image is 10^4 by 10^4 pixels. What changes?
• Recolor only the border of the connected region.