Flood Fill Easy 0 attempts
LeetCode ↗

Flood Fill

Easy GraphBFSDFS LeetCode

You're given an m x n grid of integers called image, where each value is a pixel's color. Starting from a given pixel at (sr, sc), repaint it along with every pixel reachable from it through 4-directional moves (up/down/left/right) that share the pixel's original color, changing them all to the new color. Return the resulting grid.

Input Format
Implement floodFill(image, sr, sc, color). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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]]

Example 2

Input
image = [[1]]
sr = 0
sc = 0
color = 1
Output
[[1]]
Constraints
  • 1 <= m, n <= 50
  • 0 <= image[i][j], color < 2^16
Test Cases (2)
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]]
Case 2
Args: [[[1]],0,0,1] Expected: [[1]]
Topics
GraphBFSDFS

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.

javascript
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.

JavaScript