Flood Fill Graph-Based Approach

Problem Statement❯

The Flood Fill problem is a classic image processing task. Given a 2D array image where each element represents the color of a pixel, a starting pixel coordinate (sr, sc), and a newColor, your task is to 'flood fill' the area connected to the starting pixel.

A pixel is considered 'connected' if it has the same color as the starting pixel and is connected 4-directionally (up, down, left, or right).

Replace all such connected pixels with newColor.

Examples❯

Image	Start (sr, sc)	newColor	Output
[[1,1,1],[1,1,0],[1,0,1]]	(1, 1)	2	[[2,2,2],[2,2,0],[2,0,1]]
[[0,0,0],[0,1,1]]	(1, 1)	1	[[0,0,0],[0,1,1]]
[[1]]	(0, 0)	1	[[1]]
[[0,0],[0,0]]	(0, 0)	3	[[3,3],[3,3]]
[]	(0, 0)	1	[]

Solution❯

Understanding the Flood Fill Problem

The flood fill algorithm works similarly to how a paint bucket tool works in image editing software. Given a 2D array (image), a starting pixel, and a new color, it replaces the color of the starting pixel and all adjacent pixels (up/down/left/right) that share the same original color with the new color.

Case 1: Base Case - No Fill Needed

If the starting pixel's color is already equal to the new color, no changes are needed. This is an important check to avoid infinite loops during recursion or unnecessary processing in iterative traversal.

Case 2: Small Connected Region

When the starting pixel is part of a small isolated region with a unique color, the algorithm will only modify that small region. Both DFS and BFS work efficiently here, visiting a handful of connected nodes.

Case 3: Large Connected Area

If the connected region is large (e.g., a full row or the entire image), the algorithm will traverse every pixel in that region. The graph-based approach (DFS or BFS) will visit each of those connected pixels and change their color.

Case 4: Edge and Corner Pixels

When starting from the edge or corner of the image, the algorithm behaves the same, but care must be taken to avoid accessing pixels outside the image boundary. The 4-directional neighbors must be validated to stay within bounds.

DFS vs BFS: Which One?

Both DFS (using a stack or recursion) and BFS (using a queue) are valid. DFS may use less space for shallow fills, but recursion could lead to stack overflow for very large regions. BFS uses a queue and is safer for large datasets but might consume more memory.

Algorithm Steps❯

Store the original color of the pixel at (sr, sc).
If original color is same as newColor, return the image.
Use BFS or DFS to explore from (sr, sc):

Push starting pixel to the stack or queue.
While the stack/queue is not empty:

Pop a pixel and change its color to newColor.
Push its 4-directional neighbors if they have the original color.

Return the modified image.

Code

JavaScript

function floodFill(image, sr, sc, newColor) {
  const originalColor = image[sr][sc];
  if (originalColor === newColor) return image;

  const rows = image.length;
  const cols = image[0].length;
  const queue = [[sr, sc]];

  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  image[sr][sc] = newColor;

  while (queue.length > 0) {
    const [r, c] = queue.shift();
    for (const [dr, dc] of directions) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor) {
        image[nr][nc] = newColor;
        queue.push([nr, nc]);
      }
    }
  }
  return image;
}

console.log(floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	If the starting pixel's color is already the new color, the algorithm returns immediately without modifying the image.
Average Case	O(m × n)	In most practical scenarios, a portion of the image is filled, and the algorithm visits those connected pixels once.
Worst Case	O(m × n)	If the entire image consists of the same color, the algorithm may visit every pixel, making it linear in the size of the image.

Space Complexity❯

O(m × n)

Explanation: In the worst case, the stack or queue can hold all pixels of the image if they are all connected and need to be processed.

⬅ Previous TopicRotten Oranges Problem - BFS in Matrix

Next Topic ⮕Detect Cycle in an Undirected Graph using DFS