Coding Interview Questions | Flood Fill

December 25th, 2023

Flood Fill Problem Introduction:

This summary will talk about my solution to the flood fill problem as seen on leetcode here.

Flood Fill Solution:

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

  // Base case: If the current pixel has the new color or is out of bounds, no need to fill.
  if (originalColor === newColor) {
    return image;
  }

  const rows = image.length;
  const cols = image[0].length;

  const stack: { row: number; col: number }[] = [{ row: sr, col: sc }];

  while (stack.length > 0) {
    const { row, col } = stack.pop()!;

    // Check if the current pixel is within bounds and has the original color.
    if (
      row >= 0 &&
      row < rows &&
      col >= 0 &&
      col < cols &&
      image[row][col] === originalColor
    ) {
      // Update the color of the current pixel.
      image[row][col] = newColor;

      // Push neighboring pixels onto the stack.
      stack.push({ row: row + 1, col }); // Down
      stack.push({ row: row - 1, col }); // Up
      stack.push({ row, col: col + 1 }); // Right
      stack.push({ row, col: col - 1 }); // Left
    }
  }

  return image;
}

Flood Fill Solution Summary:

This iterative flood-fill algorithm traverses the given image starting from a specified pixel (sr, sc) and changes the color of connected pixels to a new color. The algorithm utilizes a stack to perform a depth-first search (DFS) iteratively.

1. Original Color Check: The algorithm verifies if the current pixel has the new color or is out of bounds. If the pixel already has the new color or is out of bounds, it skips the fill operation.

2. Stack-Based DFS: A stack is employed to manage the pixels to be processed. The algorithm iteratively explores pixels and updates their color while ensuring all connected pixels are covered.

3. Neighboring Pixels: The algorithm checks neighboring pixels (up, down, left, right) of the current pixel. If a neighboring pixel has the original color, it is added to the stack for further processing.

4. Efficiency Consideration: The algorithm avoids unnecessary operations by skipping pixels with the new color. This optimization minimizes redundant work during the flood-fill process.