Flood Fill (Recursion)

Today I came across my first Leetcode graph problem, Flood Fill.

Here is the question:

The goal of the problem is to take a given image, in this case:

And flood fill the image starting from a specific pixel (the red 1 in the center).

Basically we need to replace any of the 1s on the graph with a 2. However if there are any other numbers on that graph (such as 0), we should leave them as they are.

Once we have replaced all the 1s with 2s, we return the modified image:

How do we approach this problem?

Let's take it one step at a time. We first need to recognize that to traverse through this graph, we can use recursion. We will need some recursive function within our algorithm to repeat until our conditions are met.

Now that we have done that, lets get rid of any possible edge cases.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
};

We know that if the image is null, then we can't do any transformation. Let's return the image if that is the case. If the image is of length 0, we also return the image, as the image is empty.

Next, we need to store our starting point in a variable. We are given our starting point through the parameters image, sr, and sc.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
};

sr represents the row, and sc represents the column.

The recursive function

To begin our recursion, lets create a function that takes in the provided parameters, plus our starting point variable, start.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
    const fill = (image, r, c, color, initCol) => {}
};

With any recursive function, we need a way to break out of the function, which is referred to as the base case. Here is what we will use as the base case:

if(r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== initCol) {
     return;
}

Remember, r represents rows and c represents columns. If we have no rows, or the row number is greater than the length of the image, we have no possible pixels to transform. This is the same for the columns.

Now that we have a base case set up, we can create our recursive logic.

Let's quickly check what all of our code looks like together:

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
    const fill = (image, r, c, color, initCol) => {
    if(r < 0 || r >= image.length || c < 0 || c >= image[0].length 
        || image[r][c] !== initCol) {
    return;
    }
  }
};

There's a little trick with this type of problem, which isn't clear at first but makes total sense once you understand how it works.

The first thing we want to do is set image[r][c] = -1

Why?
Remember in our base case, we return if image[r][c] !== initCol

What we can do with this is replace all the 1s with -1. Then, we run our recursive function. You'll see how it all comes together in just a moment.

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    let start = image[sr][sc]
    const fill = (image, r, c, color, initCol) => {
    if(r < 0 || r >= image.length || c < 0 || c >= image[0].length 
        || image[r][c] !== initCol) {
    return;
    }
    image[r][c] = -1;
    fill(image, r-1, c, color, initCol);
    fill(image, r+1, c, color, initCol);
    fill(image, r, c-1, color, initCol);
    fill(image, r, c+1,color, initCol);
  }
};

We call our recursive function 4 times here, because the problem requires us to change any pixels connected 4-directionally. Take a look at each call of fill(). In the first run, we are calling this on r-1, or the row to the left of the start point. We hit our if statement (base case), return, set the 1 to -1, and run the next fill() call. This repeats for r+1, c-1, c+1 so we are moving in all 4 directions and changing our starting point each time, until it is not possible to change anymore pixels. Now all of our 1s are -1s and our 0s still remain.

Once we have called our recursive function 4 times, we add this final line to the function: image[r][c] = color;
All this does is replace all the -1s with 2.

Finally, we call our recursive function and then return our modified image:

var floodFill = function(image, sr, sc, color) {
    if(image === null || image.length < 1) {
        return image;
    }
    const initCol = image[sr][sc];
    const fill = (image, r, c, color, initCol) => {
        if(r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== initCol) {
            return;
        }
        image[r][c] = -1;
        fill(image, r-1, c, color, initCol);
        fill(image, r+1, c, color, initCol);
        fill(image, r, c-1, color, initCol);
        fill(image, r, c+1,color, initCol);
        image[r][c] = color;
    }
    fill(image, sr, sc, color, initCol)
    return image;
};

This can be quite a tricky question, but what's great about this problem is that how we handled moving 4-directionally will apply to any other similar problems!
Give it a try, draw it out on a whiteboard, and good luck!