LeetCode Day 17 - Number of Islands (Grid BFS Algorithm)

Each cell of a grid is water or land. Find the number of islands (connected components of land cells). There are at least three solutions: DFS, BFS or DSU (also called Find&Union).

Subscribe for more educational videos on algorithms, coding interviews and competitive programming.

#Coding #Programming

[dscmtr]

Small improvement: you can mark field as visited by seting grid to '0', then you don't need matrix visited.

[Errichto]

If you participate in competitions, this is a busy weekend. Here are some reminders for you.

[mariansoltan]

I really like problems including DFS or BFS because these are the ones that are really making sense to me and for me it's a pleasure to solve them

[ebby]

Today I solved this problem using DFS all by myself for the first time ever. I want to thank you for being such a great source of knowledge. I promise that if I become as good as you, I will fly all the way down to Poland to personally thank you.

[ChandraShekhar-bycd]

@Errichto Please Continue The LeetCoder Series as it really helped us in grasping the basic as well as advanced concept to tackle any coding problems. Please take it as a Request on behalf of all the Coding Community. We need this kind of seried to

[subarukun]

WOW, your solution is clean and understandable.

[leetcodesolver]

Nice explanation. I solved this problem using DFS.

[antonyfil]

This problem came from computer graphics - filling closed areas with some color. All flood fill algorithms are applicable here.

[ChandraShekhar-bycd]

Hi Errichto, Can you please Upload a video on MO's ALGORITHM as in competitive programming it is being used extensively and I am not able to find any useful resource on that. Thanks

[SamDaBest]

This problem is the first question I solve just after I learned dfs, I was so happy to solve this at that time.

[nopethisisnotreal]

You make every question seem easy
thank you for your help!

[shubhamk]

i am new programmer, i solve problems from many coding sites and many a times I solve problems that are authored by errichto. for example on hackerrank named lisa's workbook,

[raghurrai]

Amazing! Thanks for this wonderful explanation. Really loved the refactoring techniques

[FazeelUsmani]

Great Idea!! of taking all the directions in a vector of pairs. Now, I can apply this same trick to some backtracking problems like N Queens, Rat in a Maze, Sudoku and much more. Thanks! Errichto. #cleancode
What if you solve these Leetcode challenge problems on a live stream? I mean you'll get more familiar to code while handling the crowd and also we'll gain enough experience of problem-solving. I love the way you think when one thing goes wrong you try out every other possible way. And finally, get it done. :)

[guy]

@Errichto Would love to see the DSU solution as well, or a video on that algorithm! I used a DSU solution for this but my implementation was quite naive (no path compression, splitting etc.). It would be cool to see the implementation you use for competitions.

[abhishekpadamwar]

Can you make a video explaining union find approach?

[omerronen]

Could you please post a quick tutorial on how to set up the online judge for code jam tomorrow?

[omarnader]

@Errichto can you please explain the solution using Disjoint set union???

[rohitdatta]

rather than using extra array you can just change the '1' to '0' to check!

[ambarishbanerjee]

How come your past code doesn't show up in the editor? If i have solved it before my past code shows up as soon as i click on the problem and it kind of spoils the interest to solve again.