LeetCode 733: Flood Fill

link

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: \mathcal{O}(m \cdot n), space: \mathcal{O}(m \cdot n).

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