Hello Everyone, I’d like to start a new series called “Quarantine and Code”. I saw the hashtag on twitter and it inspired me to do some tutorials while spending most of my time indoors. The algorithm I’ll be solving today is pretty famous. It’s a graph algorithm called Flood Fill and it’s very similar to Number of Islands. You can find the algorithm here on LeetCode. In this tutorial we will be using Depth First Search.
Video Tutorial
Before we get started, here is the full code.
Full Code
Input
So what is flood fill and what does it do?
If given a grid and an axis point, turn the number found at the access point into another number, as well as all of its’ equivalents. Granted, numbers signify colors, so in the example above, we are coloring all 1s into 2s. The caveat is that we can only color 1s above, below, left and right. There is no diagonal crossing, so the output of [[1,1,1],[1,1,0],[1,0,1]] will be [[2,2,2],[2,2,0],[2,0,1]]. As you can see, there is still a 1. There is no way to access it, as diagonal crossing is not allowed and we cannot change any other numbers. We are only changing the value of “oldColor” into the value of “newColor“, so any other number (0) will remain the same. Let’s begin.
The Break Down
To start off, we have our first function, floodfill, which takes 4 arguments. We are given the grid to navigate through as well as the row and column number to find the old color. We are also given a new color to change the old color to.
Following the example above, grid[1][1] will be equal to 1. So oldColor == 1. If newColor is equal to the same number as oldColor, we just return the grid as there is nothing to fill since there will be no change.
Within the same function, we call an outside function, recurse, passing in the additional variable, oldColor. This line will move outside of the floodfill function and when it returns, it will have the new grid filled.
This is where the magic begins. We are taking in the grid, row, col, newColor and oldColor passed to us by floodfill. First, we check to see if “grid[row][col]” does not equal the oldColor, because if it doesn’t, then there is no further work to do so we can just return to the previous recursive call or back to floodfill.
However, if it does equal the oldColor, 1, then of course we want to change it to a 2. so we move down to color “grid[row][col]” from 1 -> 2.
Recursion
Moving along we have four if statements that, if true, will call a recursive function.
In the first if statement, row != 0, we are checking to see if we are on the first row. Remember, index counting starts from 0, and the grid given is made up of 3 lists (0,1,2). We want to look at the number above “grid[row][col]” (or 1) to see if it is the oldColor so that we can change it to the newColor. However, if we are on the first row it is not possible to look up as there is nothing above the first, so if row == 0, we move on to the next if statement. If not, we call the recurse function with all the above arguments and minus row by 1. Following the example given, if starting row is 1, then 1-1 will give us 0, and give us access to the first row to check and change the value. So “grid[1][1]” would become “grid[0][1]”.
The second if statement follows the same logic, it’s checking to make sure we are also not on column 0, as if we were, there would be no way to look to the left of us. However, we are on column 1, so 1-1 would give us 0, so we can look to the left once the above recursive call has returned.
In the third if statement we are checking to see if we are not on the last row. Remember, the true length of the grid has 3 lists, but index counting starts at 0. row != 2 is what it equates to, and we want to make sure we are not on the last (row 2) row, as there is no way to look below us. If we are on row 0 or 1, we can look below.
Finally, we are checking to make sure we are not on the last column. Exact logic here as well. col != len(grid[0]) – 1 equates to col != 2. grid[0] has a length of 3 items, which means there are three columns. Starting at index 0, we want to make sure we are not looking to the right of column 2 (the last column) as there is nothing there.
So, that’s the explanation. Here is the before and after graph.
*If you do not still understand my explanation , please use Pythontutor.com, and plug the code in. It will walk you though step by step on what is being done in the code. You got this.
More Code
I found these two methods on Leetcode, so if you’d like to learn other ways to solve this algorithm, these are a bit more readable than other versions I’ve found online.
Method 2
Method 3
#QuarantineandCode
Que tenga un buen dia! 🙂
ColorfulCode's Journey 