Google Coding Question - Making a Large Island (Hard)
Vložit
- čas přidán 24. 07. 2024
- 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. - Věda a technologie
Every struggling coder needs a mentor like you.
Instablaster
You are the man. I spent all day doing this problem, but thanks to you, I actually understand it now. I can't tell you how much I appreciate you.
this guy does such a great job of breaking complex problems down into simple steps. goes very in depth with examples as well. great job
Thank you Michael Muinos. Simply the best explainations, when I search I first see if I find a video from Michael Muinos, if not then from Tushar Roy, if not then whatever I get.
Such a great explanation , I was able to understand every bit of it. Thank you 💛
nicely done! before watching this I watced few other videos but couldn't get anything. 11 minutes of your video and everything was crystal clear.
Great to hear!
Best and easiest solution that I could ever find for the problem. Thank You!!
Thank you for patiently going through the whole grid instead of just saying so and so and moving to code. Amazing explanation
You're very welcome!
Amazing. Your way of explanation is awesome. Keep up the good work.
I appreciate that, thank you!
super clear, right on the point. feel so lucky that I ran into this video, thanks!
This is lit 🔥 please do more graph problems
Thanks dude, will do!
The best part about his explanation is he cuts to the chase, where others are engaged in explaining things he has already arrived at the coding part!
Great Video Michael. Very clear instructions
Crystal clear explanation, I being a noob coded the solution with your thought process.
Thanks!
What an incredible solution! Thank you for this vid!
Perfectly explained. Thank you!
watching your video saved me tons of time. THX!
thank you for making all these great videos for us!
Amazing man ! your explanations made it soo easy to understand, thanks
Glad it helped!
Excellent Explanation!!!
Most satisfying code ever watched😌 keep up the work dude✌
Thank you, will do!
Awesome explanation, thank you!
Awesome explanation dude..so well explained. This is how solutions should be made. Keep up the good work!
Thanks, will do!
bloody brilliant mate
You made it so easy!!!! Thank you so much!
Thanks man. You understand what you are doing.
I appreciate that!
great explanation, much appreciated!
No problem!
GG Michael! Clear explanation. :)
Glad it was helpful!
Great explanation bro ❤😌
Great explanation thanks !!
well explained.
thanks a lot
AMAZING EXPLAINATION!!!
your videos are the best
Really loved the explaination
Thank you, I'm glad it was helpful!
One of the best explanation I seen
Thank you!
Best explanation for this problem
Michale is THE BEST.
This algo literally blew my mind!
Haha yeah it is pretty crazy
Thanks for these videos! I've been looking all over for straightforward walkthroughs of algorithms + code for this type of problem, and yours are by far the most helpful I've found :) I did want to ask, why is the time complexity O(N^2)? since the loops you highlighted aren't nested, shouldn't it be O(2 * N) which is just O(N)? Or does the recursion in the getIslandSize method factor into the calculation?
Of course, thank you for watching! Looping over a grid will be n * m. If the columns and rows are the same, it is n2.
I was initially a bit confused about this too because he said N is the number of items inside the input array, which then should be O(N).
Thank you 🙏🏾
Dude you are great..!!
Cool! Your explanation cured my panic.
Nice!
Thanks Michael, you explained very clearly with time and space complexity. One suggestion is to use proper variable names eg. instead of x, y, newRow, newColumn would be better, good job, keep going bro..
Great suggestion!
I was trying to submit this LC but couldn't get anything. You saved my day:)
With some of these hard probables you can get trapped down rabbit holes, trying to solve the problem when you don t fully understand the question, a pen and paper or white board makes them so much easier you can draw things out and quickly see and issues with logic you may otherwise had assumed was sound
how would you explain further why the space complexity os O(N^2)?
Very helpful 👍
Glad I could help!
thank you for the video
No worries!
Clear-cut Amazing
Thank you!
U the Goat
Very KIND of you :p
why grid[i][j] > 1 is wrong there? can any one explain?
Please make similar videos of interview hot problems. Focus on algorithm like this video so that we C++ people can code easily in our way after getting algorithm.
Definitely will!
best explanation
Thank you!
Is there a fan club I can join?
This is LIT
🔥🔥🔥🔥 Thanks man haha
Really good, man! Your didactics is incredible!
You should get yourself a pen; it will make your drawings much easier and better than your mouse.
Thank you very much! Actually all of my newer videos are animated now, no more drawing with a mouse haha
@@AlgosWithMichael I have 18 years of experience as a developer and now I'm practicing for an interview at Amazon. Your videos are really handy and your explanation comprehensive without being dull.
Thank you for all your efforts!
No problem at all, I wish you the best with your interviews!
Shortest bridge is similar problem please cover it
Definitely! Graph problems are the hardest imo
nice explanation . one doubt : if no of rows = n , no of cols = n , then getIslandSize -- is dfs call --- it will take O (n^2) which is equal to no of nodes traversed _ outer loop is also n^2 so total time complexity is O (n^4) Please correct me if I misunderstood Thanks
got it please ignore the question :)
Nice
Thanks!
wow beautiful
Thanks a lot!