Repeat Code With LeetCode — Floodfill
A foray into the 2D array
I purchased an annual subscription to LeetCode Premium several months ago, which was great and useful until I promptly stopped using it. The value, in my opinion, is in their well-written solutions — Flood Fill contains an exceptionally bad LeetCode Premium solution that is essentially just “Use DFS,” followed by the code.
Before I continue, let me address the elephant in the room: Another Medium blog called “Chunks” has already covered this better than I have.
The problem is ranked as an “easy,” but the candidate has to work with a 2D array. I have seen 2D arrays come up in real interviews before. CodeSignal, unless the test has changed significantly, ALWAYS has a difficult 2D array problem as #3. One company, a major financial institution headquartered in Manhattan, asked me to solve Word Search. Another company, my dream company, asked me to take a 2D array with a collection of arbitrarily placed people and to then optimally place a coffee shop such that the people had to walk a minimum distance.
Are these kinds of problems actually useful in the field? Sure. 2D array problems really do show up in the field, I just have yet to find a situation in which someone has to solve one in 45 minutes.
The Problem
Description: 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, andcolor. You should perform a flood fill on the image starting from the pixelimage[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.
Difficulty: Easy
Skills Required: 2D arrays; DFS; recursion
The Solution
On the LeetCode discussion board for this problem, one user complained that 4-directionally is confusing. I suppose a better term may have been “adjacent, non-diagonal.” Before solving this problem, it helps to work out the example on paper. As Nick White explains (his video will be linked shortly), the 1 on the bottom right never changes because it is surrounded by 0s — there is no way to possibly reach it.
In spite of being a ranked “easy,” I think there are a few things that are easy to screw up here:
- Without line 30, you get a stack overflow
- Without proper bounds checking, you get a…wait for it…out-of-bounds exception
- It’s row, column. That’s something you have to know to solve these kinds of problems, and something you may have had beaten over you in college exams. Some people suggest thinking about RC Cola, which would be an excellent mnemonic if anyone I knew drank it
- Notice the difference between lines 12 and 20. Either you get the number of rows, which is the size of the 2D array, or you retrieve any row and get its number of columns
What I wrote is based on the LeetCode solution. Nick White’s solution may be easier to digest. The code above does use recursion and does have a base case, but Nick White’s base case is more explicit.
To put this as simply as possible, you solve this problem using a recursive implementation of DFS. You need to do bounds checking, and you “fan out” to do your flood fill, keeping track of your original color in the process.
Closing Thoughts
I thought this would be longer, but I guess that’s kind of it.
I am hoping to get back into LeetCode now.
