Flood Fill | Problems

An image is represented by an m x n integer grid where image[i][j] represents the pixel value. Given a starting pixel (sr, sc) and a new color color, perform a flood fill starting from that pixel. To perform a flood fill, color the starting pixel plus all pixels connected 4-directionally that share the same original color with the new color. Return the modified image.

Example:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Sample Input

—

Sample Output

—

Constraints

1 <= m, n <= 50
0 <= image[i][j], color < 2^16

Test Cases

Case 1

Args: [[[1,1,1],[1,1,0],[1,0,1]],1,1,2] Expected: [[2,2,2],[2,2,0],[2,0,1]]

Topics

Graph BFS DFS

Approach: DFS

Start from the source pixel and recursively fill all 4-directional neighbors that share the same original color. Skip if the new color equals the original color to avoid infinite loops.

function floodFill(image, sr, sc, color) {
  const orig = image[sr][sc];
  if (orig === color) return image;
  function dfs(r, c) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
    if (image[r][c] !== orig) return;
    image[r][c] = color;
    dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
  }
  dfs(sr, sc);
  return image;
}

Time Complexity: O(m × n)

Space Complexity: O(m × n) for recursion stack

Saved in this browser only. Private to you.