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

[@dscmtr686]

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

[@sananyuzb]

That's possible if you can change the input. If you are not allowed to change the input, you should use visited array. It is good practice to ask that type of question during interview, so you can construct correct solution.

[@Errichto]

Cool idea!

[@liwaiyip1769]

@@sananyuzb I think it is ok to go for the solution with changing the input. You can simply say that you can make a clone of the input if they do not allow changing the input. That still costs O(H*W) space. But if they allow changing the input, it will improve the space complexity.

[@fauzanwaseem6436]

Nice idea bro

[@Errichto]

If you participate in competitions, this is a busy weekend. Here are some reminders for you. Today (Saturday) is Topcoder Open 1A codeforces.com/blog/entry/76067 Tomorrow (Sunday) is Google Code Jam 1B codingcompetitions.withgoogle.com/codejam EDIT: and Google Kickstart in a few hours, thanks for pointing this out codingcompetitions.withgoogle.com/kickstart

[@ebby41]

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.

[@AnkitJosh]

Ehhh keep going champ!

[@AAAAAA-gj2di]

Hello please can anyone tell me why dfs or bfs is implied to count those

@@AAAAAA-gj2di because with dfs/bfs you will get to all the other possible "1"s from the starting "1". If after a bfs cycle a "1" hasn't been visited, then it is not a neighbor of any of the already visited "1"s.

[@AAAAAA-gj2di]

@ suppose I assume a "1" as my root node....then which "1"s are it's children?

[@AAAAAA-gj2di]

@ sorry mate i'm very new to coding

[@mariansoltan1318]

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

[@arinroday302]

The best part is that debugging is also too hard

[@ChandraShekhar-by3cd]

@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 continue.....

[@ChandraShekhar-by3cd]

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

[@vigneshsekar2001]

Yes Errichto pls do

[@suprabhatkumar151]

Checkout this video and other related to MO's algo in the playlist kzbin.info/www/bejne/babRlY2CdpiSqLc

[@ChandraShekhar-by3cd]

@@suprabhatkumar151 Thanks a lot for the link..it really gives all the idea from basics to understand it more deeply.

[@SamDaBest]

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

[@anuragpatro8979]

Hey, do you mind telling how you used DFS? BFS makes sense as you check all adjacent ones for the same island, how would you go about DFS?

[@joshuaclark9425]

@@anuragpatro8979 The only difference is you add all the neighbouring land cells to a stack instead of a queue. So it explores as far as it can in one direction first rather than spreading out evenly from the starting point.

[@israkulhaquetusher3256]

@@anuragpatro8979 you have to run N dfs if there are N island ( the idea behind is flood fill )

[@lovvyparhar393]

Exactly same thing happened to me

[@anuragpatro8979]

@@joshuaclark9425 Got it, thanks

[@subarukun8001]

WOW, your solution is clean and understandable.

[@abhishekpadamwar2333]

Can you make a video explaining union find approach?

[@leetcodesolver9092]

Nice explanation. I solved this problem using DFS.

[@shubhamk840]

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

[@worklifeandstuff]

I enjoyed it too, mate!!!

[@raghurrai]

@@worklifeandstuff hue hue

[@nopethisisnotreal1434]

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

[@antonyfil]

This problem came from computer graphics - filling closed areas with some color. All flood fill algorithms are applicable here. en.m.wikipedia.org/wiki/Flood_fill

[@harshpatel105]

Ah thanks!

[@omerronen2329]

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

[@kevinhwa]

Can you make a video on DSU for this problem?

[@pritamrao3256]

Refer code n code youtube channel he has a wonderful playlist on that topic

[@omarnader686]

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

[@CodingWithUnity]

Cool series, enjoying it!

[@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. :)

[@guy491]

@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.

[@namanchetwani2028]

You are literally amazing.😶

[@climbnexplore1187]

Thanks for the hardcoding tip!!

[@dhrubankadutta2245]

Can anyone provide a good resource online to learn graph, tree and heaps? I always find that every series misses some part or the other.

[@randomrandom316]

The MIT lectures though a little slow paced are quite good for the fundamentals. kzbin.info/www/bejne/fqW2pnRuZbaHr9E

[@dhrubankadutta2245]

@@randomrandom316 Thanks

[@ivanp4740]

Robert Sedgewick and his algorithms course on Coursera The best course I have ever seen. Good structure, code examples(of any algorithm/data structure), visualization, proofs and properties of algorithms. He covers almost every topic which is important for coding interview

[@deep_swamp]

This is an awesome Python resource focused solely on mastering data structures: donsheehy.github.io/datastructures/

[@andreykarayvansky9549]

I solved this task using just DFS. I also wonder is union/find a must to know algorithm? I often find if a task can be solved using UF (DSU) there is always some other less academic way to solve it. I wonder what is your opinion. Thanks!

[@ej9806]

BFS is better than DFS because you won't get stack overflow

[@andreykarayvansky9549]

You can implement DSF with no stackoverflow issues

[@andreykarayvansky9549]

I actually used UF many times. I even remember I solved this task using UF. The problem is that if I want to use it (and that does not happen often) I need to look it up since this algorithm is quite easy to forget

[@ambarishbanerjee414]

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.

[@ihopethiscommentisntabusiv4670]

@Errichto could you explain why this is linear runtime? Why is it not O(n^2) because you have the outer loops + the BFS traversal.

[@rahul0000nm]

Could you please explain the code you start with? The one which helps you debug your solution locally

[@ChandraShekhar-by3cd]

@Errichto What is the time complexity for this approach??

[@catalingriu8817]

How to create a cpp file with my template from terminal? (when i type "geany a.cpp" it's emty)

[@lavishgarg4274]

kzbin.info/www/bejne/m4G9dp6Yl8tmnMU

[@catalingriu8817]

@@lavishgarg4274He didn't talk about my question. I watched the video 3 times.

[@Errichto]

if a.cpp doesn't exist, geany opens an empty file I have file templates.cpp and I copy by hand from it, or type "cp templates.cpp a.cpp" in terminal

[@sandipjana5553]

Hi Errichto.. at 0:45 you said it can be solved using DSU and then you said we need to know "some particle technique" . Can you mention the name of the technique once. Thanks in advance

[@fauzanwaseem6436]

Nice job bro 👍

[@mohnishsatidasani7552]

How to Apply DSU over a matrix grpah without flatting the matrix or grid?

[@i.m.anonymous8492]

Respected Sir, I am unable to understand how the input output is working for the given question, i.e. how is output for example 1 = 1 and that off example 2 = 3.

[@shaunbillonesshauntunado7277]

Can you help me with a question in islanda as well?

[@PavanKumar-jt5mq]

I think a dfs written as lambda function would be a bit shorter implementation. I was expecting this 😅.

[@rohitdatta6379]

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

[@abdoulayediagne2976]

Indeed! And then space complexity will be O(1)

[@baukabaiorazov5277]

I think we don’t need visited. We can change ‘1’ to ‘0’ without extra memory.

[@mogovanjonathan]

Hy Errichto, you posted 2 moths ago a video named "C++ Bitsets in Competitive Programming". Could you please help me with the c++ solution of the first problem (the one with the worker during 1 month) using popcount, and how to make 2 3 5 6 8 (it there were only 8 day) in 01101101, wich is in decimal 109? It would be very helpful! Thank you for reading this and answering!

[@dfhfdhahhs9803]

I don't think 01101101 is decimal. Seems to me that they respond to 1,2,3,4,5,6,7,8 counting from left to right. 1 meaning it's there and 0 it's not 01101101 -> 0,2,3,0,5,6,0,8.

[@mogovanjonathan]

@@dfhfdhahhs9803and how to I change this 0,2,3,0,5,6,0,8. into 01101101 using bitset? thanks

[@MatthewJDrake]

What keyboard do you use? (Sorry if you get asked that a lot...)

[@nitishraj-pj2ef]

Did by using DFS

[@codeguy21]

Guys I have a doubt the real programming that we work as a software engineer is that easier than competitive programming,

[@shashikantpunia9019]

depends on individual interest. However development is quite easy compared to cp

[@vaibhavvashist238]

can you tell me how to get motivated and maintain consitency?

[@deshabhaktg6530]

GOD❤️🔥😍

[@musicfan1695]

errichto do you drink coffee too often ?

[@prakash_77]

As someone who doesn't know BFS,DFS or Find/Union(DSU), this solution went over my head. 😑

[@Player-ub9tg]

There is no way of solving this without that algos

[@gamegamesoumic]

I did it with DFS.

[@mr.mystiks9968]

I feel like BFS and DFS problems are least likely to come up in interviews just because they’re all very similar and don’t require as much intellect as say Dynammic Programming or Greedy algorithms.

[@akulsinghal216]

Well then you haven't solved good bfs/dfs problems.

[@ivanp4740]

Not agree, there is a lot of dfs/bfs problem that will struggle you a lot :) Especially the ones which combine different techniques For example this one: leetcode.com/problems/robot-room-cleaner/ which is a combination of DFS and backtracking. Can't say that this is a very hard problem(especially when you got a hint about backtracking :D) but anyway... Also can add that there is a lot of problem with DP that don't require a lot of intellect. Actually, a lot of dp questions can be solved manually. You just write brute force recursive solution, then you make a drawing and you will see that there is a lot of repeated calls, then you just use memorization(or bottom-up as memory optimization) . This is not hard but visualization is very important because repeated calls can be non-obvious(that's why it looks hard) About greedy - agree. For me, it's the hardest topic. Can't understand where this will work and where will not

[@williambillemeyling5647]

Grid problems are my favorite graph problems! :)

[@aimelodies5]

One suggestion , please use white board it will be more intutative for us .

[@dr.darkfurygaming9174]

When you forget to upload video😑

[@AlexandrBorschchev]

Do I have impostor syndrome if i watch Errichto?

[@John-Weak]

Dumb me used simple old recursion for this

[@baibhabmondal1740]

lol same. Idk why but i keep going back to recursion, even for today's problem. :P

[@John-Weak]

@@baibhabmondal1740 same energy bro,but dynamic is better for today's problem

[@naveenrawat6278]

First.

[@BharatPatidar_juriz]

second xD

[@mariansoltan1318]

Seventh