^ Image of a heron on an old bridge support in Richmond, VA that I made during an MS paint challenge
Implementing Flood Fill
Today, Benjamin Arnavand I tackled a depth-first-search (DFS) leetcode problem called flood fill. Aging myself, I was secretly excited about this problem because it’s the algorithm behind MS paint’s classic “fill” behavior. When I was nine, I got frustrated by this mechanism, which didn’t always “squeeze through” diagonal “gaps” in the pixels like I hoped it would, but it did have a knack for still finding a way through some opening I accidentally left in my outlines. You can’t have it all.
Turns out, this is exactly the behavior leetcode asks us to create - for each pixel that needs to be changed to a new color, check all four of it’s neighbors (not all eight!) to see if they are the same as the original color, and continue changing their colors until hitting the edge or exhausting all same-color neighbors.
Even as a team, we were a bit spooked by the term “depth first search”. We discovered the correct approach during our fifteen minute pseudo-coding exercise, but then looked up answers before attempting to implement it. I believe this was a mistake, as we robbed ourselves of the full opportunity to debug our own implementation.
That said, once we verified our approach was a valid one, we were able to implement it within ten minutes. This is what we came up with in python:
def floodFill(self, image, sr, sc, color):
original_color = image[sr][sc]
rows, columns = len(image), len(image[0])
if original_color == color:
return image
def dfs(r,c):
if r < 0 or r >= rows or c< 0 or c>= columns:
return
if image[r][c] != original_color:
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 imageLater I translated it to JavaScript:
function floodFill(image, sr, sc, color){
let originalColor = image[sr][sc]
if (originalColor === color) return image
let rows = image.length
let cols = image[0].length
function dfs(sr, sc){
if (sr < 0 || sr >= rows || sc < 0 || sc >= cols) return
if (image[sr][sc] !== originalColor ) return
image[sr][sc] = color
dfs(sr+1, sc)
dfs(sr-1, sc)
dfs(sr, sc+1)
dfs(sr, sc-1)
return
}
dfs(sr, sc)
return image
}Gotchas
- When porting to JavaScript I made the mistake of checking if
image[sr][sc] === color, instead of original color likeimage[sr][sc] === originalColor. Thecoloris the color we are changing each pixel to, but only if it is the same color as the original color - Although in python this doesn’t seem necessary, the
image[rc][sc]does seem to need to be evaluated after all of the boundaries checks, otherwise we run the risk of checking for an index on a row that doesn’t exist, throwing an error.
DFS vs. BFS
The only real difference with breadth-first-search (BFS) is that instead of following each path all the way to the end before starting the next one, we evaluate each neighbor before moving in. Because BFS can’t really be done recursively, this can be understood best by changing the DFS implementation above into an iterative one and then comparing it with iterative BFS.
Iterative DFS
var floodFill = function(image, sr, sc, color) {
if (image[sr][sc] === color) return image;
const originalColor = image[sr][sc];
const rows = image.length;
const cols = image[0].length;
const stack = [[sr, sc]];
while (stack.length > 0) {
const [r, c] = stack.pop();
if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] !== originalColor) {
continue;
}
image[r][c] = color;
stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
}
return image;
};Iterative BFS
var floodFill = function(image, sr, sc, color) {
if (image[sr][sc] === color) return image;
const originalColor = image[sr][sc];
const rows = image.length;
const cols = image[0].length;
const queue = [[sr, sc]];
while (queue.length > 0) {
const [r, c] = queue.shift();
if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] !== originalColor) {
continue;
}
image[r][c] = color;
queue.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
}
return image;
};Pretty similar, right? The only different is that we are applying a queue.shift() on our array (and calling it a queue for that matter) instead of a stack.pop(). The .shift() is FIFO - we are making sure to execute our operations in the order they come up, and not, I dunno, starting our side quests as they come up.
.pop(), meanwhile, gives us LIFO, or a stack, where we keep drilling down into next generations of our search as we discover them, only “back tracking” once we’ve followed a path all the way to the end.
DFS Diagram
BFS Diagram
Implementation thoughts
- Re:gotcha #2, I wonder if instead of checking for boundaries I could just do a
try/catchand let the boundary errors happen:
function floodFill(image, sr, sc, color){
let original_color = image[sr][sc]
if (original_color === color) return image
function dfs(sr, sc){
try{
if (image[sr][sc] !== original_color ) return
image[sr][sc] = color
dfs(sr+1, sc)
dfs(sr-1, sc)
dfs(sr, sc+1)
dfs(sr, sc-1)
return
} catch {
return
}
}
dfs(sr, sc)
return image
}
let arr = [[1,1,1],[1,1,0],[1,0,1]]
console.log(floodFill(arr, 1, 1, 2 ))Things I learned
Nested function declarations can be👌🏼
Although declaring a function inside of another function can be dangerous for scope-declaration collision concerns, it can also be really convenient for scope-declaration redundancy avoidance. I’ve been burned by this in the past during a mock interview, so initially I had some resistance when Benjamin wanted to do this, but he changed my mind. A recursive function declared inside of a parent function that can call it allows global variables to be declared once and awkwardly passed through a section time to the recursive function, even though they may not change.
Default parameter values are OP
That said, one of the coolest things I’ve learned about recursive functions recently is that because by nature each new function is nested inside a previous generation of itself, any variable declared in the first generation (possibly as a default value for a parameter), never needs to be redeclared.
Continuing on that train of thought - if default variables can be useful in this way, can they also be used to remove the recursive-function-parent-function pattern entirely? For example, something like:
let someFunc = function(someVar, initial = false){
if (initial === true){
let someGlobalVariable = 4
}
}
Okay so in writing the above I realized no, this isn’t a good way to create global variables, because in this case the “global” variable needs to be wrapped inaccessibly inside of a conditional.
However, what are the limits to the evaluations we can run inside of the parameters?
let someRecursiveFunc = function(someVar, anotherVar = () => {
let someDeclaredVar = 1 + 2 / 4 // some math
return someDeclaredVar
}
) {
// wow really not sure how to indent
var doSomethingWithAnotherVar = anotherVar++
}^ I don’t see why this isn’t possible. It is a bit confusing though. Never has clear indentation practices been so important or, in this case, so inadequate.
DFS and BFS have similar forms, but distinct strengths
Another thing I learned was that, at least in this case, depth-first-search (DFS) and breadth-first-search (BFS) are very similar. In fact, the only difference in code seems to be that DFS employs pop() in order to perform LIFO (last-in-first-out), whereas BFS uses shift to achieve FIFO (first-in-first-out).
As far as differences in performance, here is a comparison.
DFS
- memory usage generally lower than BFS
- Good for finding a path if several exist
BFS
- Good for finding THE path if only one exists
- Guaranteed to find shortest path to something while iteration occurs, not after
- Can be slower in cases where the “goal” is deep in the structure
Conclusions
The flood fill problem is a really nice way to visualize the tree-like behavior recursion of both BFS and DFS. I would like to explore other BFS and DFS use cases to understand them better.