NUMBER OF ISLANDS - Leetcode 200 - Python

0:00 - Conceptual Solution
5:00 - Coding

#Coding #Programming #CodingInterview

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[bibiworm]

Very nice channel that helps me a lot. But one thing that I notice is the lack of discussion of time and space complexity every so often. I'd really appreciate it if you could discuss it in every single one of your videos. Thank you so much.

[amn]

Nice vid! I find that the naming convention for r, c and rows, cols could be better because they are used multiple times in different "levels" and is quite confusing which rows/cols/r/c we are talking about.

[arnabpersonal]

using that range might be expensive instead explicitly use 0<= r+dr < len(grid)

[tumarisyalqun]

It's amazing how clear your explanations are. Thank you for the videos!

[yu-changcheng]

My DFS solution is very similar to word search but somehow, it is easier. As we just keep eliminating the 1 until there is no 1 left and count that as an island. Then continue the algorithm to search next 1, until all the grids have been searched.

class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
count = 0
if not grid: return 0

def dfs(i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
return
if grid[i][j] != "1":
return
if grid[i][j] == "1":
grid[i][j] = "#"

dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)

for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
count += 1
dfs(i, j)
return count

[sna]

Your videos are very helpful. Thaks a lot.
In this code, when you say [1, 0], you are actually moving one row vertically down by doing row+dr. So, we are not moving right along x-axis. Instead, we are moving down.

Similary, for the direction [-1, 0] -> It is upward
[0, 1] -> Right (Moving right by col + dr)
[0, -1] -> Left

Please correct me if I am wrong.

[nishantingle]

It is a standard algorithm from computer graphics called Flood Fill which builds upon DFS

[littlebox]

Thanks for the great explaination. if I understand this right here is what should be done for this problem - iterate all elements in the array, for each element if it is 1 and not visited then run dfs/bfs to mark all adjacent 1 as visited and increase the island number by 1.

[shelllu]

by far the best explanation I've seen for this problem. Thank you!!

[ianpan]

For this particular question, I find DFS more straightforward (and also much more concise).

[rogdex]

Neetcode is the reason leetcoding feels like therapy

[xxRAPRxx]

Great video! Small nit: In order to turn your BFS code into *true* DFS code, you must not just transform popleft() into pop() but call visit.add(...) immediately after q.pop()

[sauravdeb]

Hats off to the best explanation out there.

[shivaranjinimithun]

Very informative channel. I am not just learning intuition for building algorithms, but also coding in Python. Thank you very much

[abdosoliman]

by the way, you can do the same without visited set just change the value of the from '1' -> '2' in the gird. this will make the memory complexity O(1) since we don't care about the graph anyway so it's ok to modify it

[parsasedigh]

I think neetcode mentions the directions wrong. [0, 1] -> right, [0, -1] -> left, [1, 0] -> below and [-1, 0]-> above

[HaAnh-vtqq]

Nicely but actually in BFS function, when you meet the value '1', you can adjust it to '2', this help you no need to use visit_set

[il]

Is using bfs faster for this problem? If that's the case, how do we determine when to use bfs instead of dfs?

[victoriac]

I do have a question, why do we have to search for four directions, why can't we search for only right and down directions?

[_bazmac]

I love your solutions and explanations Neetcode. You make easy what others make hard. In this particular case I'm a little worried in terms of complexity since it seems is O(n)3? Can it be done with less time complexity?Thanks.