leetcode month day 9: flood fill

A bit of a break working on a friend’s art business launch; still working on that, but made some time to come back to leetcode month today.

Today’s problem is flood fill; another easy-rated one. This is again a recursion problem, and the tricky bit is as usual preventing extra recursion that doesn’t need to happen.

Doing this one is made a lot easier by unifying the calling sequence with a helper function that adds an

Go-specific issues for me were properly extracting the dimensions of a two-D array and having to do that with a pointer. Since we want to alter the array we’re flood filling, we need to pass a pointer to it so that we can actually modify the source array.

I got tripped up by the termination condition. In addition to “are we outside the bounds of the array”, we also need to check if this cell needs filling at all (is it the fill color already? Is it the color we want to fill?).

I did need a couple runs with debug prints in to spot where my recursion was going wrong; the first cut didn’t have the “is this already the right color” test, and I was able to catch that one with the supplied test cases. It. failed on the submit because I wasn’t checking for “is the fill already done” case.

How did I do relative to other cases? Pretty good! Runtime in the top 92%, memory usage a quarter of a percent short of the 100th percentile. Should be a pass in an interview. (I did get this one at Thumbtack, and came out with a solution similar to this one, except I used an 8-cell neighborhood when a 4-cell will work. Too many Game-of-Life programs.)

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
    eligibleColor := image[sr][sc]
    return *floodFillHelper(&image, sr, sc, color, eligibleColor)
}

func floodFillHelper(image *[][]int, 
                     sr int, sc int, 
                     fillColor int, 
                     eligibleForFill int) *[][] int {
    if sr < 0 || 
       sc < 0 || 
       sr > len(*image) - 1 || 
       sc > len((*image)[0]) - 1 ||
       (*image)[sr][sc] != eligibleForFill ||
       (*image)[sr][sc] == fillColor {
       return image
    }
    
    (*image)[sr][sc] = fillColor
    
    floodFillHelper(image, sr-1, sc, fillColor, eligibleForFill)
    floodFillHelper(image, sr+1, sc, fillColor, eligibleForFill)
    floodFillHelper(image, sr, sc-1, fillColor, eligibleForFill)
    floodFillHelper(image, sr, sc+1, fillColor, eligibleForFill)
    
    return image
}