LeetCode: Flood Fill Solution

Approach: DFS

Recursively traverse in 4 directions

Implementation

1var floodFill = function (image, sr, sc, newColor) {
2  const [m, n] = [image.length, image[0].length]
3  const visited = Array.from({ length: m }, _ => Array(n).fill(false))
4
5  const valid = (r, c) => {
6    return (
7      0 <= r &&
8      r < m &&
9      0 <= c &&
10      c <= n &&
11      !visited[r][c] &&
12      image[r][c] === image[sr][sc]
13    )
14  }
15
16  const traverse = (r, c) => {
17    if (!valid(r, c)) return
18
19    visited[r][c] = true
20
21    traverse(r - 1, c)
22    traverse(r, c - 1)
23    traverse(r + 1, c)
24    traverse(r, c + 1)
25
26    image[r][c] = newColor
27  }
28
29  traverse(sr, sc)
30
31  return image
32}

References

Original problem