Flood Fill App Implementation | Dataford Interview Questions

Pinterest's image editor represents a canvas as a rectangular grid of color values. When a user selects a pixel, implement a flood fill that recolors the entire four-directionally connected region containing that pixel.

A cell belongs to the region if it has the same original color as the starting cell. Return the modified canvas. Diagonal cells are not connected.

Formal Specification

Implement fill_canvas(canvas, sr, sc, new_color).

canvas is a non-empty list of non-empty lists of integers, where each integer represents a color.
sr and sc are valid zero-based row and column indices.
new_color is an integer.
The function must recolor the target region in place and return canvas.

Use an iterative traversal so the algorithm does not depend on Python's recursion limit.

Constraints

1 <= len(canvas) <= 500
1 <= len(canvas[0]) <= 500
Every row has the same length
0 <= sr < len(canvas)
0 <= sc < len(canvas[0])
0 <= canvas[r][c], new_color <= 10^9

Function Signature

def fill_canvas(canvas, sr, sc, new_color):

Your question is Flood Fill App Implementation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem