Grind 75 Question 9: Flood Fill
This is where sauce gets real.
The Problem
An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.
You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].
To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.
Return the modified image after performing the flood fill.
The First Attempts
Reading over this had me like:
Then it had me like:
Then I sat down and truly tried to understand what was going on and spent a half day pondering how exactly to approach the problem.
I’m sure I’m going to have to read all about graphs to fully solve it, but I decided to do things My Way. Here’s the initial (probably unnecessarily long and not working) code:
/**
* @param {number[][]} image
* @param {number} sr
* @param {number} sc
* @param {number} color
* @return {number[][]}
*/
var floodFill = function(image, sr, sc, color) {
image[sr][sc] = color;
if(image[sr - 1][sc] > 1) {
image[sr - 1][sc] = color;
};
if(image[sr + 1][sc] > 1) {
image[sr + 1][sc] = color;
}
if(image[sr][sc -1] > 1) {
image[sr ][sc - 1] = color;
}
if(image[sr][sc + 1] > 1) {
image[sr - 1][sc + 1] = color;
};
for(i = 0; i < image.length; i++) {
for(j = 0; j < image.length; j++){
if(image[i][j] > 1 && image[i - 1][j] === color) {
image[i][j] = color;
}
if(image[i][j] > 1 && image[i + 1][j] === color) {
image[i][j] = color;
}
if(image[i][j] > 1 && image[i][j - 1] === color) {
image[i][j] = color;
}
if(image[i][j] > 1 && image[i][j + 1] === color) {
image[i][j] = color;
}
}
}
return image;
};Time to plug it in and let it work its *~*magic*~*.
…
Of course, the magic doesn’t work. I look at it some more. It should be working — except that I’m searching for some negative index values. So I fix it up, and, hey-o! It works!
/**
* @param {number[][]} image
* @param {number} sr
* @param {number} sc
* @param {number} color
* @return {number[][]}
*/
var floodFill = function(image, sr, sc, color) {
image[sr][sc] = color;
if(sr > 0 && image[sr - 1][sc] > 0) {
image[sr - 1][sc] = color;
};
if(sr < image.length - 2 && image[sr + 1][sc] > 0) {
image[sr + 1][sc] = color;
}
if(sc > 0&& image[sr][sc -1] > 0) {
image[sr ][sc - 1] = color;
}
if(sc < image.length - 2 && image[sr][sc + 1] > 1) {
image[sr - 1][sc + 1] = color;
};
for(i = 0; i < image.length; i++) {
for(j = 0; j < image.length; j++){
if(i > 0 && image[i][j] > 0 && image[i - 1][j] === color) {
image[i][j] = color;
}
if(i < image.length -2 && image[i][j] > 0 && image[i + 1][j] === color) {
image[i][j] = color;
}
if(j > 0 && image[i][j] > 0 && image[i][j - 1] === color) {
image[i][j] = color;
}
if(j < image.length - 2 && image[i][j] > 0 && image[i][j + 1] === color) {
image[i][j] = color;
}
}
}
return image;
};I am 100% positive that it won’t work if I submit it, though. Upon testing…runtime error! Fix it some more: wrong answer.
Time to visit my old pal Neetcode and learn about graphs.
The Solution
Turns out Neetcode didn’t cover this one! So I watched this guy’s video, which is a decent explanation. My approach wasn’t wrong, exactly, but it wasn’t right, either. The missing key was, once again, a recursive function. Gah! Here’s the correct code:
/**
* @param {number[][]} image
* @param {number} sr
* @param {number} sc
* @param {number} color
* @return {number[][]}
*/
var floodFill = function(image, sr, sc, color) {
if(image[sr][sc] === color){
return image;
}
fillPixels(image, sr, sc, image[sr][sc], color);
return image;
function fillPixels(image, sr, sc, color, newColor) {
if(sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length || image[sr][sc] != color){
return;
}
image[sr][sc] = newColor;
fillPixels(image, sr+1, sc, color, newColor);
fillPixels(image, sr, sc+1, color, newColor);
fillPixels(image, sr-1, sc, color, newColor);
fillPixels(image, sr, sc-1, color, newColor);
};
};To explain it as best I can:
- If the pixel color matches the new color, just return the entire image. It’s dumb, but I believe this is called an “edge case”. I got a wrong submitted answer on Leetcode without it.
- Barring that, call the fillPixels function on the target pixel, and when it’s done, return the completed image.
- And what does fillPixels do in the background? Well, it takes a look at the pixel.
- If it’s out of bounds in any way, or if it doesn’t match the original color of the pixel being modified, move on without changing anything.
- If it isn’t out of bounds and matches the original color, change it to the new color.
- And because it’s a recursive function, we do that to every square touching the colored pixel. And again — somehow it knows when to stop executing. When every touched pixel has been changed to the new color. The end. Question done.
What I Learned
- More about recursive functions — namely, that I need to be more on the lookout for them!
- Depth-first searches. Or, I will learn about them. As soon as I’m done with this post and get a free moment.
- Learned all about…uh I forget what they’re called. Maybe this counts as a graph. 2-D array? Unsure. But I discovered on my own that array[0].length gives me the length of an individual row. Cool!
mins
read
