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! 👏💯👩💻
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)
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.
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
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
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. =)
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?
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
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?
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
# 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
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.
