Google Coding Interview Question - Number of Closed Islands (LeetCode)

Here is a step by step explanation of another "island" problem asked at Google.

🎧 Join the community Discord: https://discord.gg/aVWsAaaCtT
💰 Support me on Patreon: https://www.patreon.com/michaelmuinos
🔗Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos
📂Follow me on Github: https://github.com/MichaelMuinos

We have another addition to the "island" problem family. This problem is asked at Google and can be solved using a Breadth-first search or Depth-first search. For this tutorial, I go over the DFS solution because it is a bit easier to understand in comparison to the BFS solution.

To solve this problem, we must identify what constitutes a "closed" island. A closed island is a group of 0's that are entirely surrounded by water (1's). The trick to solving this problem is identifying that any island that touches the perimeter of our matrix will for sure NOT be a closed island. The reason this is the case is because if our island is on the perimeter, it is impossible for it to be surrounded since it is at the maximum bounds already.

With this information, we do not need to iterate over our perimeter, only the elements within the center of our matrix. As we are iterating, when we encounter a 0, we perform our DFS starting at that position and change any 0's we see to -1 to illustrate that we have visited that position. An alternative to this approach is to have a 2D boolean array instead of modifying our input; however, modifying our input is easier to write and involves less code!

Finally, when we are converting our 0's to -1's, if our position is on the perimeter and it is a 0, we know it is not a closed island and we can return false from our function that is determining if it is a closed island or not.

Видео Google Coding Interview Question - Number of Closed Islands (LeetCode) канала Michael Muinos