# #733 Flood Fill

Solved at: 2022-09-05

## Question

An image is represented by an `m x n`

integer grid `image`

where `image[i][j]`

represents the pixel value of the image.

You are also given three integers `sr`

, `sc`

, and `color`

. You should perform a **flood fill** on the image starting from the pixel `image[sr][sc]`

.

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 `color`

.

Return *the modified image after performing the flood fill*.

## Solution

`class Solution:`

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 = []

queue.append([sr, sc])

while queue:

[r, c] = queue.pop(0)

if visited[r][c]:

continue

if image[r][c] != original:

continue

image[r][c] = color

visited[r][c] = True

if r > 0:

queue.append([r-1, c])

if r < len(image) - 1:

queue.append([r+1, c])

if c > 0:

queue.append([r, c-1])

if c < len(image[0]) - 1:

queue.append([r, c+1])

return image

I did BFS, but it seems possible to do this in recursion too.

## Results

- 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.

## Complexity Analysis

- Time Complexity: $O(N)$, where N is the number of pixels in the image
- Space Complexity: $O(N)$, the size of the implicit call queue