Number of Islands - Breadth First Search (LeetCode)
Vložit
- čas přidán 28. 07. 2024
- 📚 Graph Problem Tips Video: • Coding Interview Prep ...
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
Number of islands is one of the most popular questions on Leetcode and in coding interviews in general. It is a graph problem that has been known to be asked at many top companies such as Amazon, Google, Facebook, Microsoft, Apple, Bloomberg, Adobe, Uber, and many more.
Number of islands is a graph based question where we must count the islands in a 2D matrix containing only 0's and 1's where 1's are land and 0's are water. An island is any 1's connected horizontally or vertically together, but not diagonally. To solve this problem, you can use a BFS, DFS, or union find algorithm, but for this tutorial I go over the breadth-first search approach. For a BFS, we must initialize a queue to add the position we are currently looking at to continue adding any neighbors in the up, down, left, and right directions. Anytime we encounter a 1 (land), then we add 1 to our count for an island and change it to water so that we don't double count the same island.
The time complexity of our solution is going to be O(N*M) where N is the number of rows and M is the number of columns in our matrix. The space complexity will be O(min(N*M)) where N is our row length and M is our column length. - Věda a technologie
You have a really nice crystal clear way of explaining things, please keep making videos!
Thank you for the kind words, more videos to come!
One of the best explanations. Clear and concise. Thank you
Dude nice, simple and clean. Watched other tutorials but couldn't understand them.
Big upgrade from your previous explanations a couple months back with the whiteboard. Definitely one of the best explainers on youtube with these new videos! Keep up the great work!
Much appreciated!
Thank you for always discussing time and space complexities. Keep it up!
Thanks, will do!
I really appreciate the effort you have put to make the video and also explanation was on point
I love the in depth explanation with illustrations.
Thank you!
This dudes videos are 101% the best on DSA you'll find anywhere 🔥👍🚀
Thank you SO much!
coordinates is such smart idea
Yea, the first time I learned it, I was like 😱😱😱😱
Thank you very much, The graphical explanation at the start really made it very clear
Glad it was helpful!
Brilliant. Please do video every day. It would be of great help!!
Haha can't do everyday, but hopefully 1 to 2 times a week consistently!
@@AlgosWithMichael That will work too..
Superb Job. learnt quite a bit. thank you.
Thank you for watching!
Nice job @Michael Muinos
Thanks so much!
i solved it using dfs technique and was quite easy method
Thank you so much!!
You're welcome!
Nice! Vote for 2 videos/week.
Thank you!
thanks for the video
what is the point of using a queue when it will always have one value ?
I remembered you have one DFS solution before
in R*(col) + C what if size of C > R then it will give extra values
will the queue always have a length of one?
Very well explained... Thanks for making it easy for us... Why you din't use recursion instead like the one you used in closed island?
I do have another (older) video going over this problem using recursion. I wanted to specifically cover the BFS approach in this video
Whats the point of doing 2d to 1d and 1d to 2d
Kind bars? Awesome !
haha yep!
Can you make a video on path with maximum probability . By the way your explanation is awesome
Yea, I think I have seen that problem. And thank you!
the optimum solution, better than other youtubers and their skills is not at your level yet.
Haha thank you! I don't know though some of those competitive programmers would wipe the floor with me
@@AlgosWithMichael but you taught this problem better than them, take heart in that!
Can you please please please do Number of Islands II?? I can't get to understand solutions explained by anyone else other than u...
Hi Michael, can you please also do one for 547. Friend Circles since it's very similar to this question but different. However I find it very hard to understand the difference. Thank you so much in advance!
Definitely, I was planning on doing that problem
@@AlgosWithMichael Thank you so much Michael!!
Why did you use bfs and not dfs?
High-caliber content!
Thank you!
why don't we increase islands in the if statement in fillWithWater?
We are increasing islands, but right before we call the `fillWithWater` function. All attached land to the first encounter of land will get filled if that makes sense
Where is the link in the description 2d to 1d array conversion?
It is in the description, but I'll link it here as well :)
czcams.com/video/tMSdjPKFRD4/video.html
I can't find the URL for the 2D -> 1D coordinate :(
czcams.com/video/tMSdjPKFRD4/video.html
I thought you and Kevin Naughton are the same person
hahaha
I think there's too many references to previous content and it makes this pretty hard to follow as a person landing on this video directly.