LeetCode: Flood Fill Solution

Recursive DFS

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

Comments

Loading comments...

Tags

leetcode

array

matrix

dfs

Next Post

LeetCode: Merge Two Binary Trees

Sep 21, 2021

"You know you don't get bonus points for squishing all your code into the least number of lines" - someone

Previous Post

LeetCode: Longest Substring Without Repeating Characters

Sep 18, 2021

Sliding window uses two pointers?

HoningJS

Search Posts