0733 Flood Fill
Solved at: 2022-09-05
An image is represented by an
m x n integer grid
image[i][j] represents the pixel value of the image.
You are also given three integers
color. You should perform a flood fill on the image starting from the pixel
To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with
Return the modified image after performing the flood fill.
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
original = image[sr][sc]
visited = 0 for i in image[0 for j in image]
queue = 
[r, c] = queue.pop(0)
if image[r][c] != original:
image[r][c] = color
visited[r][c] = True
if r > 0:
if r < len(image) - 1:
if c > 0:
if c < len(image) - 1:
I did BFS, but it seems possible to do this in recursion too.
- Runtime: 125 ms, faster than 43.36% of Python3 online submissions for Flood Fill.
- Memory Usage: 14 MB, less than 89.56% of Python3 online submissions for Flood Fill.
- Time Complexity: , where N is the number of pixels in the image
- Space Complexity: , the size of the implicit call queue