If source color and target color are the same, nothing to do. Otherwise, we remember the source color, color the cell and its four neighbors. A cell is filled at most once.
Time: , space:
.
class Solution:
def fill_from(self, image, row, col, src_color: int, target_color: int) -> None:
def is_valid_coord(r, c) -> bool:
return 0 <= r < len(image) and 0 <= c < len(image[0])
image[row][col] = target_color
for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
neibor_row, neibor_col = row+dr, col+dc
if not is_valid_coord(neibor_row, neibor_col):
continue
if image[neibor_row][neibor_col] != src_color:
continue
self.fill_from(image, neibor_row, neibor_col, src_color, target_color)
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
if image[sr][sc] == color:
return image
self.fill_from(image, sr, sc, image[sr][sc], color)
return image
Leave a comment