Google Graph Interview Question! | Leetcode 200 - Number of Islands

FAANG Coding Interviews / Data Structures and Algorithms / Leetcode

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[obscureautumnfrost]

I usually solve this using BFS. It helps me to understand similar graph problems that have matrices in them.

[davidespinosa]

Good job ! Some small adjustments:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
return
grid[i][j] = "2"
dfs(i-1, j) ; dfs(i+1, j) ; dfs(i, j-1) ; dfs(i, j+1)
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
res += 1
dfs(i, j)
return res

[soumyarupmukhopadhyay]

As an interviewer at a FAANG, it’s a red flag if you’re changing the input. Use a visited matrix to keep track of where you’ve been rather than changing the 1s to 2s.

[luisguillermoballesteros]

Thanks a lot @GregHogg. Excellent explanation. Just a little optimization: the only directions needed are Right (0, 1) and Down (1, 0). You are scanning the grid from left to right and up to down. Here is a version that take account that and copy the grid:

def numberOfIslands(grid):
m = len(grid)
n = len(grid[0])
temp_grid = []
for row in grid:
temp_grid.append(row.copy())

num_islands = 0

def dfs(position):
i, j = position
directions = [
(0, 1), # Right
(1, 0), # Down
# (0, -1), # Left
# (-1, 0) # Up
]
for i_off, j_off in directions:
i2 = i+i_off
j2 = j+j_off
if i2 >= 0 and i2 < m and j2 >= 0 and j2 < n and temp_grid[i2][j2] == 1:
temp_grid[i2][j2] = 2
dfs((i2, j2))

for i in range(m):
for j in range(n):
if temp_grid[i][j] == 1:
num_islands += 1
temp_grid[i][j] = 2
dfs((i, j))

return num_islands

grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1]]
result = numberOfIslands(grid)
print(result)

[giantbush]

Can be 22 lines. You can remove the assignment stmt in the for loop. You already setting visited cell to '2' in the dfs function.

[gamename]

Nice I have a friend who is studying math and at his first semester he had this question I had time so I went with him you can actually solve it way cleaner with a recursive algorithm that changes every touching field into it’s own number

[ThuyPham-rxks]

Thanks so much for the short video. I enjoyed it a lot. Hope you keep making those 😁

[nolanrata]

I think it is possible to solve this by visiting each node once and avoiding recursion, on the first 1 encounter paint it to a set color and paint the adjacent vertices with the same color, and increment a counter for the amount of islands; if a node is already painted, paint the adjacent vertices that are 1 to the same color, except if an adjacent vertex is already painted with a different color, decrement the island counter and set that second color to be the same as the first color (could be done with pointers).

[OctagonalSquare]

I built a parser to make tilemaps from text files for a Python class where I built a 2D platformer, and it’s almost the exact same logic

[Barioth]

Hey, nice problem, I think that you should not use recursion here since the number of recursive calls can be in O(n) (with n being the number of nodes). Use a stack to remember which vertices you have to visit next.

[kyaki]

Bros did not just say he was gonna use a dfs for that💀💀💀

[lizzard]

I was asked this question in 2022, I guess they are still with this question

[cercruder]

Lmao I literally was asked this today. Glad I watched

[artinzareie]

To be more accurate, it is not BFS, it is Flood Fill

[jaugustussmith]

Has anyone used anything like this in any of their work?

[zhilkevich]

It would be nice to have an island definition here

[Gkcrafting]

Am I the only one to think he looks like _jeb?

[musaifbangi]

If.you know graph theory you would know what is this