Algorithms: Solve 'Connected Cells' Using DFS

[@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! 👏💯👩‍💻

[@harrymuir6625]

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)

[@sophiaatn5339]

you're not at all.

[@Stewty1]

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

[@srinivasnangunuri1313]

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

[@jasonlu3603]

Agreed, matrix problems are the toughest since they have so many components to solve together. LeetCode has a problem very similar.

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

[@The.Dark.Panther]

Damn. That's a pity... :/

[@codingwitharman5329]

You can always re-apply, right??

[@DadBodSwagGod]

So here’s the thing... This was written over a year ago I AM working at Google right NOW

[@codingwitharman5329]

@@DadBodSwagGod That's great man!!

[@radsimu]

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

[@athletics365]

@Flynn Boston that was the weirdest plug I've ever seen

[@wasd3108]

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

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

[@sampathkumar3405]

that is what i thought..the elements vertically up and down, elements horizontal get skipped in that case right?

[@syedmuhammadzaeemhasankazm7740]

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

[@paulb6611]

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.

[@lameow76]

because of the recursive calls there can be cells down in the group whose up's or left's neighbor cells would be un-visited

[@abhishekkthakur1]

Jeez, you are awesome. Period.

[@oceanview-u8q]

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. =)

[@caesar18fifa63]

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?

[@Secretzstolen]

Size is the name of the variable and int is the variable type (integer)

[@Secretzstolen]

Re: Q2 - yes that's basically what the recursion is doing. Although it's also marking off the cells is has visited already to a zero, so that way there won't be any duplicate checking

[@Alexander-bk6oy]

any idea on how to prevent that diagonal check ?

[@narayanasai]

will it work for [[0,1],[1,0]]

[@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?

[@morubalok]

avoiding the current element

[@SundarRajansrgm]

Also should it be if (r != row && c != col) , AND instead of OR ?

[@alokesh985]

It won't matter since we're setting mat[row][col] to 0

[@lokeshs9449]

Instead we make size=0

[@learnersparadise7492]

@@alokesh985 it would matter as size is 1

[@shaunbillonesshauntunado7277]

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

[@balluvwdwadi8995]

You can use recursion

[@QiMU01]

This is awesome!

[@muhammadmohibkhan3745]

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?

[@dunnithful]

size being greater than maxRegion in all other cases is not true. you can find a region of size 3, then find a region of size 7, then find a region of size 4. with your logic, size would always equal the last found region (4 in this case, which is less than 7). im sure you already know this by now but this should answer it for anyone else reading this thread in the future

[@radsimu]

no need for line 20

[@operationsus9117]

Anyone know why this solution doesnt work with javascript?

[@Stewty1]

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

[@adikatz3501]

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

[@b.m.7033]

Yes, I think so. I needed to add valid row/column checks to the inside for loops.

[@AlMan123xyz]

The condition is already present in row 10

[@SpiritOfIndiaaa]

Need a bit more details when explaining the traversal of maxRegion

[@imanbio]

# example: finding islands on a map in Python import numpy as np map1 = np.array([[0,0,0,1,1,0,0], [0,1,0,0,1,1,0], [1,1,0,1,0,0,1], [0,0,0,0,0,1,0], [1,1,0,0,0,0,0], [0,0,0,1,0,0,0]]) print(map1) def findIslands(inputMap): Islands = [] # the list of found islands and their nodes: [[nodeSet1], [nodeSet2], ...] mapRows, mapColumns = inputMap.shape for r in range(mapRows): for c in range(mapColumns): if (inputMap[r, c] == 1) & (not discovered([r, c], Islands)): # function discovered checks if the node [c,r] has been found before newPoint = [r, c] newIsland = discoverIsland(newPoint, inputMap) Islands.append(newIsland) return Islands def discovered(newPoint, Islands): discoveredBefore = False for i in range(len(Islands)): if newPoint in Islands[i]: discoveredBefore = True return discoveredBefore def neighborsFind(newPoint, inputMap): mapRows, mapColumns = inputMap.shape neighbors = [] for rw in range(max(newPoint[0] - 1, 0), min(newPoint[0] + 1, mapRows - 1) + 1): for cm in range(max(newPoint[1] - 1, 0), min(newPoint[1] + 1, mapColumns - 1) + 1): if inputMap[rw, cm] == 1: neighbors.append([rw, cm]) return neighbors def discoverIsland(newPoint, inputMap): island = [newPoint] currentIndex = 0 while currentIndex < len(island): neighbors = neighborsFind(island[currentIndex], inputMap) for i in range(len(neighbors)): if not neighbors[i] in island: island.append(neighbors[i]) currentIndex += 1 return island islands = findIslands(map1) islands

[@ONCE_AGAIN]

Time complexity? O(n^4)?

[@apnihorrorduniya]

Omg are you human?

[@somerandomguy000]

no, she just a good communicator and person capable of copying from a book the solution of a problem

[@IsmailHossain-ov5ir]

I think you should also use C++ to solve hackerrank problems.

[@hippityhoppity657]

it should be "r!=row && c!=column" not ||

[@HanifCarroll]

I was looking at that and thought the same thing, but second guessed myself because she didn't correct that mistake with editing like she did the others. Thanks for this comment.

[@abhishekbose6989]

its correct