Flood fill algorithm in javascript

Learn how to solve the flood fill algorithm in javascript.

Flood fill also called as seed fill is an algorithm to determine the area connected to the given node in a multi-dimensional array.

The most common use of this is to use it as a bucket to fill connected, same colored areas in the painting apps Or in the images to replace the pixels with same color.

Example

Input:
const arr = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 2, 2, 2, 2, 0, 0, 0],
[0, 0, 0, 2, 2, 0, 0, 0],
[0, 0, 0, 2, 2, 2, 2, 0],
[0, 0, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 2, 0],
]

//Replace all all the similar pixels at arr[3][3] with 3. 
//Which is basically replace all 2 with 3.
Output:
[
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 3, 3, 3, 3, 0, 0, 0],
[0, 0, 0, 3, 3, 0, 0, 0],
[0, 0, 0, 3, 3, 3, 3, 0],
[0, 0, 0, 0, 0, 3, 0, 0],
[0, 0, 0, 0, 0, 3, 3, 0],
]

Flood fill algorithm in javascript.

The flood fill algorithms works by replacing all the similar elements 4-directionally. Above, below, before, after and plus any pixels connected to those in all the directions.

Implementation

• We will create a function which will fill the color by calling itself recursively in all the 4-directions.
• But before that check if the input to be replaced and the new input are same or not.
• If they are same then return the original array because it will result in infinite loop.
• Otherwise check all the boundaries and fill the color only if it is within the bound and is not different input.

const floodFill = (image, sr, sc, newColor) => {
    //Get the input which needs to be replaced.
    const current = image[sr][sc];
    
    //If the newColor is same as the existing 
    //Then return the original image.
    if(current === newColor){
        return image;
    }
    
    //Other wise call the fill function which will fill in the existing image.
    fill(image, sr, sc, newColor, current);
    
    //Return the image once it is filled
    return image;
};

const fill = (image, sr, sc, newColor, current) => {
    //If row is less than 0
    if(sr < 0){
        return;
    }

    //If column is less than 0
    if(sc < 0){
        return;
    }

    //If row is greater than image length
    if(sr > image.length - 1){
        return;
    }

    //If column is greater than image length
    if(sc > image[sr].length - 1){
        return;
    }

    //If the current pixel is not which needs to be replaced
    if(image[sr][sc] !== current){
        return;
    }
    
     //Update the new color
     image[sr][sc] = newColor;
    
    
     //Fill in all four directions
     //Fill Prev row
     fill(image, sr - 1, sc, newColor, current);

     //Fill Next row
     fill(image, sr + 1, sc, newColor, current);

     //Fill Prev col
     fill(image, sr, sc - 1, newColor, current);

     //Fill next col
     fill(image, sr, sc + 1, newColor, current);
    
}

Input:
console.log(floodFill([[1,1,1],[1,1,0],[1,0,1]], 0, 1, 2));

Output:
[[2,2,2],[2,2,0],[2,0,1]]

Time complexity of flood fill algorithm.

As we have to update the array in all the 4 – directions, each function call will run in O(M * N) where M is the numbers of rows and N is the number of columns and we are calling the 4 times recursively so the time complexity is O(4 * M * N) = O(M * N).

Space complexity.

Same goes for space complexity each function call will make 4 function calls for all the rows and columns so it will be O(4 * M * N) = O(M * N).