20) Flood Fill (Again)

Tackled this again with Seamus! Communication can be difficult when referring to visually complicated graphs - I initially failed to grasp the nuance of how we needed to save the color of our initial tile, and couldn’t quite catch up quickly enough until Seamus and Paul walked me through line by line using an example, at which point it made sense that we needed to save this information so we could check each successive tile against it.

Time to completion: 24 minutes

// given row column color
// 
 
function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
    let q = [] // first in first out (stack is last out )
    // shift and push (vs push and pop)
    let visited = new Set()
 
    // first thing in queue?
    q.push([sr, sc])
 
    const offsets = [[-1, 0], [0, -1], [1, 0], [0, 1]];
 
    const target = image[sr][sc];
    image[sr][sc] = color;
 
 
    while (q.length){
        // do stuff!
        const current = q.shift()
        if (visited.has(current.join("_"))) continue
        visited.add(current.join("_"))
        
        const [row, col] = current
        
        
        for (const [rO, cO] of offsets){
            const nextR = row + rO;
            const nextC = col + cO;
 
            if (nextR < 0 || nextR >= image.length) {
                continue;
            }
            
            if (nextC < 0 || nextC >= image[0].length) {
                continue;
            }
 
 
            if (image[nextR][nextC] === target){
                // Actually change the color in place!
                image[nextR][nextC] = color;
                q.push([nextR, nextC]);
            }
        }
    }
 
    return image;
 
};

Okay I’m going to go through this with annotations:

 
function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
    let q = [] // first in first out (stack is last out )
    // shift and push (vs push and pop)
    let visited = new Set()
 
    // first thing in queue?
    q.push([sr, sc])
 
    const offsets = [[-1, 0], [0, -1], [1, 0], [0, 1]];
 
    const target = image[sr][sc];
    image[sr][sc] = color;
 
 
    while (q.length){
        // do stuff!
        const current = q.shift()
        if (visited.has(current.join("_"))) continue
        visited.add(current.join("_"))
        
        const [row, col] = current
        
        
        for (const [rO, cO] of offsets){
            const nextR = row + rO;
            const nextC = col + cO;
 
            if (nextR < 0 || nextR >= image.length) {
                continue;
            }
            
            if (nextC < 0 || nextC >= image[0].length) {
                continue;
            }
 
 
            if (image[nextR][nextC] === target){
                // Actually change the color in place!
                image[nextR][nextC] = color;
                q.push([nextR, nextC]);
            }
        }
    }
 
    return image;
 
};

Review of BFS vs DFS tradeoffs

So we obviously started with a BFS approach

Paul Batchelor

Recommends the graph traversal section of the Algorithm design manual BFS vs. DFS graph traversal. Here’s a free PDF! Sorry Steven Skiena - please buy this mans book.