Repeat Code With LeetCode — Number Of Islands
Flood the islands to get rejected by Amazon
This is going to be a pretty quick post — not because the problem is easy, per se, but because it’s really not that different from Flood Fill. In fact, you can think of the core algorithm as a flood fill problem. Traverse every square in the matrix, flood fill every island, and return the final count. This does not just work on an intuitive level, but on a pun level as well. Flood the islands.
The Problem
Difficulty: Medium
Skills Required: 2D arrays, graph theory, DFS (depending on implementation)
Description: Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
The Solution
If you are like me and have LeetCode Premium, you may find yourself staring at their solution for a while. It works, but I did not find it 100% clear why it worked until I thought about it for a little while. Essentially, you are applying the “flood fill” operation repeatedly. Every “1” signifies an island, increments the count, and triggers a DFS. Every time you do this, have DFS set the starting value to 0. If you work this out with an example, I think it will become clear why the “repeated flood fill method” will not double-count anything from the same island, but will instead return the correct number of islands.
Kevin Naugthon Jr’s solution is a little clearer than mine, but I chose to write mine the way I wrote Flood Fill. When you see a recursive function, you are probably used to seeing something like this:
- Some base case is stated, causing the function to exit prematurely under certain conditions (most commonly when a value is NULL)
- Some recursive call is made
Kevin’s code has the base case segregated like that. Mine still has a base case, but it is implicit. Eventually dfs will stop being called because of how the grid’s bounds are defined.
He also verifies that the grid is not empty. I got the solution accepted by LeetCode, but in an interview this would be important.
LeetCode Continuation
I am not sure what else to say about this particular problem. This is the second problem I have done in a while on LeetCode, after a pretty long break.
Someone in the comments section wrote that Amazon failed them on the example LeetCode solution. The reason was that they did not support actually modifying the original grid. Instead, the candidate was expected to make a new 2D array and keep track of things that way.
At this point, I have been doing this for a pretty long time. Someone on r/leetcode asked how many problems a candidate has to do. The best answer was that this is the wrong metric — it’s more about having the ability to solve a random medium in 30–45 minutes.
Which kind of begs the question — is this worthwhile? That’s the million dollar question. I have already complained about how it is not, and some commenters responded that LeetCode questions are used to assess problem solving ability. I guess what I still dislike is Jeff Atwood’s “most candidates can’t even solve the simplest problems” attitude, but that starts to bleed into other topics.
A coding interview is not standardized, as there is no universal “license to code” or “general programming certification” to insert into job applications. Yet somehow we have found ourselves in a world where so many companies model their interview process after Google that entire courses and boot camps have emerged that specifically coach people in the ability to pass programming interviews.
I guess all of this is to say — no problem is necessarily easy, at least not at first. The worst interviewers you encounter will look at you like the problem they just assigned is the easiest thing they have ever seen, and how dare you waste their time with your pitiful brute force implementation. Clearly your inability to solve “number of islands” in 30 minutes with an optimal algorithm means you have never written code before, you incompetent imposter.
We all have to start somewhere, we are all steadily learning, and sooner or later we all suffer the consequences of interviews that are not that similar to actual tasking for software engineers.
