Flood Fill

Why it belongs on this sheet

This is a lightweight grid traversal problem and a good way to rehearse DFS boundary checks.

Pattern

Grid DFS with base guards

Approach

Start from the source cell and recursively paint neighboring cells that match the original color. Stop on out-of-bounds or mismatched cells.

Java solution

class Solution {
  public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int original = image[sr][sc];
    if (original == color) {
      return image;
    }

    fill(image, sr, sc, original, color);
    return image;
  }

  private void fill(int[][] image, int row, int col, int original, int color) {
    if (
      row < 0 || col < 0 || row == image.length || col == image[0].length
      || image[row][col] != original
    ) {
      return;
    }

    image[row][col] = color;
    fill(image, row + 1, col, original, color);
    fill(image, row - 1, col, original, color);
    fill(image, row, col + 1, original, color);
    fill(image, row, col - 1, original, color);
  }
}

Complexity

• Time: O(m * n)
• Space: O(m * n) in the worst recursive case

Interview note

The early return when the new color matches the old color avoids infinite revisits.