733. Flood Fill

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
BFS (Breadth-First Search)	Use a queue to explore connected pixels level by level. Start from the given pixel, add it to queue and visited set. For each pixel, change its color and explore all 4 adjacent pixels that have the original color and haven't been visited. Continue until queue is empty.	\(O(m \times n)\)	\(O(m \times n)\)

Implementation

PythonJavaScriptGo

from collections import deque
class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        originalColor = image[sr][sc]
        if originalColor == color:
            return image

        m, n = len(image), len(image[0])

        delta = ((0, 1), (1, 0), (-1, 0), (0, -1))

        queue = deque([(sr, sc)])
        seen: Set[Tuple[int, int]] = set()
        seen.add((sr, sc))
        while queue:
            r, c = queue.popleft()
            image[r][c] = color
            for dr, dc in delta:
                row = r + dr
                col = c + dc
                if (0 <= row <= m-1) and (0 <= col <= n-1):
                    if image[row][col] == originalColor:
                        if (row, col) not in seen:
                            queue.append((row, col))
                            seen.add((row, col))
        return image