Repaint the connected region of a picture

This is flood fill. Remember the starting colour; if it already equals the new colour, return a copy unchanged. Otherwise walk from the start with a stack, repainting each matching pixel and pushing its neighbours. Each pixel is repainted once: O(R·C) time and space (the copy).

The early return when the colours match prevents an infinite loop in versions that use the colour itself as the 'visited' mark.

Repainting as you push doubles as the visited set.

Paint programs use this with scanline tricks to process whole runs at a time.

STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def repaint(picture: list[list[int]], r: int, c: int,
            colour: int) -> list[list[int]]:
    out = [row[:] for row in picture]
    old = out[r][c]
    if old == colour:
        return out
    out[r][c] = colour
    todo = [(r, c)]
    while todo:
        y, x = todo.pop()
        for dy, dx in STEPS:
            ny, nx = y + dy, x + dx
            if (0 <= ny < len(out) and 0 <= nx < len(out[0])
                    and out[ny][nx] == old):
                out[ny][nx] = colour
                todo.append((ny, nx))
    return out

Common mistakes

• Forgetting the same-colour case and looping forever.
• Repainting pixels that only touch diagonally.

Mention the same-colour edge case before you start; interviewers often test it.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you fill only the border of the region?

   Show hint

   Repaint pixels that have at least one neighbour outside the region.

2. What if the picture is huge?

   Show hint

   Use an explicit stack or a scanline fill to avoid deep recursion.