Repaint A Connected Region
Problem
A grid of numbers represents the colours of an image. Given a starting cell and a new colour, repaint the starting cell and every cell reachable from it by steps up, down, left or right that pass only through cells of the starting cell's original colour. Return the grid.
Examples
Input: grid = [[1, 1, 1],
[1, 1, 0],
[1, 0, 1]], row = 1, col = 1, colour = 2
Output: [[2, 2, 2],
[2, 2, 0],
[2, 0, 1]]
Why: the bottom-right 1 only touches the region diagonally, so it staysInput: grid = [[5]], row = 0, col = 0, colour = 3
Output: [[3]]Input: grid = [[0, 0],
[0, 0]], row = 0, col = 0, colour = 0
Output: [[0, 0],
[0, 0]]
Why: edge case, repainting with the same colour changes nothingHints
0 / 3
The region is defined by connectivity, so the work is a traversal outward from the starting cell rather than a scan of the whole grid.
You need a way to avoid visiting a cell twice. Painting a cell with the new colour already marks it, as long as the new colour differs from the old one.
Remember the original colour and return straight away if it equals the new one. Otherwise push the start onto a stack. Pop a cell; if it is inside the grid and still has the original colour, paint it and push its four neighbours. Stop when the stack is empty.
Solution
This is a plain depth-first flood outward from the start, where the paint itself serves as the visited marker: once a cell holds the new colour it no longer matches the original and will not be expanded again. That trick only works when the two colours differ, which is why equal colours return early; without that check the same cells would be pushed forever. An explicit stack keeps deep regions from exhausting the call stack. Every cell in the region is painted once and pushes four neighbours, so time is O(rows * cols) and the stack is O(rows * cols) in the worst case.
def repaint(grid, row, col, colour):
old = grid[row][col]
if old == colour:
return grid # nothing to do, and no endless loop
stack = [(row, col)]
while stack:
r, c = stack.pop()
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == old:
grid[r][c] = colour # painting doubles as the visited mark
stack += [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
return grid
print(repaint([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)) # -> [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(repaint([[5]], 0, 0, 3)) # -> [[3]]
print(repaint([[0, 0], [0, 0]], 0, 0, 0)) # -> [[0, 0], [0, 0]]Stuck on the idea rather than the code? Flood Fill covers it.