Here is a step by step explanation of a Google coding question involving DFS/BFS rated as hard!
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
►Number of Islands Explanation Video: • Technical Interview Qu... `
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos
This is another video explanation going over the infamous "island" problems called "Making a Large Island". This problem is asked at Google and involves the use of a Breadth-First Search OR Depth-First Search. This problem is rated as "hard".
To solve this problem, we must first loop over our initial 2D matrix filled with 0's (water) and 1's (land). We keep track of the groupings of islands using an 'islandId' in order to label the appropriate sizes of the islands. We then save these island id's inside of map and tie the island size to it.
Once we are finished tallying up all of the sizes of the islands inside of the map, we can now iterate over our 2D matrix again, but this time checking all neighbors around only 0's to determine if changing it to a 1 will allow for a larger island size.
The time and space complexity for our solution is O(N^2) where N is the number of elements we have in our 2D matrix.