Flood Fill
- 2 min read
- Array
- LC-Easy
3 years ago
Solution
- Can solve with Breadth-first Search
- No need to use visited set because the color of the pixel indicates whether we've already visited it or not:
- Whenever we visit a cell, we change it's color to the new color. If we check for this, we don't need to add it back to the queue.
- One important condition to remember here is that we need to check if the original starting pixel is the new color. If it is, we don't need to do anything and return.
- If we don't check for this, the algorithm goes into an infinite loop.
| Time | Space | Explanation |
|---|---|---|
O(mn) | O(mn) |
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
starting_color = image[sr][sc]
vis = set()
nrows, ncols = len(image), len(image[0])
q = deque([(sr, sc)])
while q:
for _ in range(len(q)):
r, c = q.popleft()
if (r, c) not in vis:
vis.add((r, c))
image[r][c] = color
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nr, nc = r + dr, c + dc
if nr >= 0 and nr < nrows and nc >= 0 and nc < ncols and (nr, nc) not in vis and image[nr][nc] == starting_color:
q.append((nr, nc))
return image