Flood Fill

How it works

BFS explores pixels level by level, processing all pixels at distance 1 from the start before those at distance 2, and so on. While DFS dives deep immediately, BFS spreads outward uniformly. Both achieve the same result for flood fill, but BFS uses a queue instead of the call stack.

The key is to color pixels when adding them to the queue, not when processing them. This prevents adding the same pixel multiple times and keeps the queue size manageable.

Steps

1. Store the original color and check if it equals the new color (early return if so).
2. Initialize a queue with the starting pixel coordinates.
3. Immediately change the starting pixel to the new color.
4. While the queue is not empty:
   • Dequeue a pixel.
   • For each of the four neighbors, if it is within bounds and has the original color, change it to the new color and enqueue it.
5. Return the modified image.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns in the image.

Things to watch for

Infinite Loop When New Color Equals Original Color

If the starting pixel already has the target color, the algorithm will infinitely revisit the same pixels since the color change that normally marks pixels as visited never happens. Always check if originalColor == newColor at the start and return immediately if true.

Not Storing the Original Color Before Modifying

The flood fill must only spread to pixels matching the original color of the starting pixel. If you check against the current pixel color after already modifying some pixels, you may either skip valid pixels or incorrectly include pixels of the new color. Store the original color in a variable before any modifications.

from typing import List
from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        orig = image[sr][sc]
        if orig == color:
            return image

        m, n = len(image), len(image[0])
        q = deque([(sr, sc)])
        image[sr][sc] = color
        dirs = [(1,0), (-1,0), (0,1), (0,-1)]

        while q:
            r, c = q.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == orig:
                    image[nr][nc] = color
                    q.append((nr, nc))

        return image

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int orig = image[sr][sc];
        if (orig == color) return image;
        int m = image.size(), n = image[0].size();
        queue<pair<int,int>> q;
        q.emplace(sr, sc);
        image[sr][sc] = color;
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto &d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == orig) {
                    image[nr][nc] = color;
                    q.emplace(nr, nc);
                }
            }
        }
        return image;
    }
};