Algorithms: Solve 'Connected Cells' Using DFS

Learn how to solve 'Connected Cells' using depth first search algorithm (DFS). This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell.

[Secretzstolen]

This is a fantastic and elegant solution. My first attempts at super difficult problems tend to be more verbose lol so it's great to see simpler solutions. My first language was JS, then I worked in Python & TypeScript. Watching these videos & reading your book is actually getting me more comfortable with Java which is great. TypeScript was 👌 as I'm now familiar with types, which really helps in strictly typed languages. Thank you for this video and all your work! 👏💯👩‍💻

[Stewty]

I am learning this for a coding interview, thank you for sharing this !

[srinivasnangunuri]

Daummmnn. this has cleared me up of so many gaps related to solving matrix island problems!

[harrymuir]

OMG! This video is awesome, I'm software engineer and it's so difficult to me solve matrix problems like this one (I hope to not be only the one who feels like that wayt)

[DadBodSwagGod]

Wow...this is an amazingly useful video

No joke, if I saw this in August of last year, I would be working at Google right now

[radsimu]

if you cannot destroy matrix, you can increment visited 1's and then change any non zero value back to 1

[lajollaaa]

matrix[row][column]=0 looks good to avoid unnecessary search again. boundary check is everywhere in examples i've seen(rat in maze or find bomb or find bike in xx company campus, find anything in multi array, etc) to avoid 'out of list'. any missing minor case check can be added always since the video is just to share idea. as long as interviewee can write this in whiteboard in less than 15 or 20 min, still good enough to pass cause 1 hr is too short to check everything anyway. =)

[syedmuhammadzaeemhasankazm]

Hey Gayle, your solution is so simple and awesome!
Can you please tell me, what is the Big O of this code? And how could we have optimised it? (if optimisation was possible)
Thanks in advance.
From what I can understand, we could have perhaps used memoization to reduce extra steps. Am I right? Although I am not sure what would have been complexity then

[SundarRajansrgm]

should it be if (r != row && c != col), AND instead of OR ? we just want to avoid that specific current position. Anyhow the code works because of matrix[row][column]= 0

[SpiritOfIndiaaa]

Need a bit more details when explaining the traversal of maxRegion

[caesarfifa]

Q1. What does int size mean? is int size the value stored inside a particular matrix entry? Q2. Is this implementation of DFS basically saying check all adjacent matrix entries to the starting entry. whichever adjacent entry has a one, then make it the new starting entry and do the same thing all over again?

[shaunbillonesshauntunado]

I need a help with disconnected islands, can you help me?

[Alexander-bkoy]

any idea on how to prevent that diagonal check ?

[muhammadmohibkhan]

wont the size be equal to 0 if there is no region (no 1 in grid)? then size and maxRegion would both be 0, whereas size would be greater than maxRegion in all other cases. So do we really need to compare size with maxRegion instead of directly assigning size?

[wasd]

6:40 there's literally no difference if you check at recursion start or before recursion start, how is it "so many more problems"?

[operationsus]

Anyone know why this solution doesnt work with javascript?

[Stewty]

would be great if you have a python version of the code too

[nickgoupinets]

Why do we need to check for "if (r != row || c != col) {"? We are setting matrix[row][col] to 0 anyways, so it won't matter technically, or I am off?

[paulb]

Actually I found another optimization. Since the array is starting from the top left and moving to the bottom right, you actually don't need to check the cell to the left or up from it because every time you check it, it will already have been set to 0.

[adikatz]

What will happen if row/column are equal to 0? I think we will get an exception...