NUMBER OF ISLANDS - Leetcode 200 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Solve it yourself: neetcode.io/problems/count-nu...
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.

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@olivejuice1985]

Is it O(n) time because we're not visiting the same element twice?

[@subhendurana6457]

Sir you are a hope! Your content is super awesome! Liked it subscribed it. I think I should start paying for bit of amount ..it' free but invaluable!

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

[@thelonearchitect]

The time complexity is in the order of O(n) because of DP using the visited array. And because of this array, the space complexity also is in the order of O(n).

[@kartheekreddy994]

Algorithm uses BFS, and time complexity and space complexity can be verified from BFS

[@tumarisyalqun7327]

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

[@am3n89]

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.

[@raidenmotors3033]

It doesn't help that he refactors (r + dr) to (row + dr)...

[@arnabpersonal6729]

using that range might be expensive instead explicitly use 0

[@akhilraj6891]

I think so!

[@djmeredith6520]

Beautiful clean solution and well explained. Thank you!

[@shivaranjinimithun]

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

[@nishantingle1438]

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

[@MichaelShingo]

building an app right now with drawing functionality, and I'm finding myself coming back to graph algorithms for a very practical purpose!

[@sauravdeb8236]

Hats off to the best explanation out there.

[@shelllu6888]

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

[@NeetCode]

Happy it was helpful! 🙂

[@yinglll7411]

Such a beautiful explanation! Thank you!

[@AnkitYadav-cw8oo]

cant thank you enough..I just saw it once and and it was done..very nice explanation 💯

[@sna241]

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.

[@brickoutside]

I caught that as well. I guess it doesn't really matter since you check all four directions anyways, the order doesn't matter. Good observation regardless.

[@potatocoder5090]

Thanks for this comment! I was super confused about the directions. This helped :)

[@hernanzavala2791]

Yep saw this as well, just wanted to confirm. Thanks for commenting! :)

[@ayushijain3340]

Well done nicely explained :-)

[@Mamtagoyal27]

Really nice explanation. Can you also please explain the logic for treasure islands problems?

[@littlebox4328]

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.

[@anhngo581]

ye, that's a good summary!

[@ianpan0102]

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

[@netraamrale3850]

Thanks alot for such an easy explanation, coding made easy. This helped me to understand question and solution both

[@varunshrivastava2706]

To be honest he didn't explain this question completely like if you look at his latest videos he completely discusses each and every step but in this question, he didn't explain a lot of stuff.

[@akhma102]

Brilliant Explanation!

[@shravanne902]

Thanks!

[@NeetCode]

Hey Shravan, thank you so much! I really appreciate it 😀

[@jx7433]

Thanks for the excellent video! Does anyone know the complexity of this?

[@rogdex24]

Neetcode is the reason leetcoding feels like therapy

[@user-ju5un2wh5w]

brilliant

[@yu-changcheng2182]

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

[@eba-pachi]

much easier solution, thanks!!

[@augustoferreira238]

This video helped me a lot. Thanks for that!

[@NeetCode]

Glad it helped!

[@LeonardoAndradeSantana]

Really nice explanation. Thanks man

[@HaAnh-vt7qq]

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

[@khagharhimerov3462]

by doing so, can I assume the space complexity will be reduced to O(1)?

[@SATISH17869]

@@khagharhimerov3462 but we're still using a queue, so the space complexity will remain the same.

[@khagharhimerov3462]

@@SATISH17869 , Thanks!

[@begenchorazgeldiyev5298]

Isn't it a bad practice to alter the passed in value cos I was thinking of changing visited 1's to 0's?

[@TCErnesto]

@@begenchorazgeldiyev5298 yes it is, but since this is not production code might as well do it but let the interviewer know that you're aware

[@rishikaverma9846]

absolutely love this channel

[@il5083]

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

[@_bazmac7285]

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.

[@toose8388]

I don't think so. Although he's looping for m x n, he's only doing something meaningful (BFS) for nodes that haven't been visited. So basically we are just visiting each node once, i.e. O(m x n). But technically, yeah, this is O((m x n)^2)

[@PhanNghia-fk5rv]

ty, i've improved al;ot after watching these video, ty so much

[@kafychannel]

great work thanks so much

[@VishnuVardhan-gr6op]

Great solution. Please go thourgh Time and Space complexity as well

[@xmnemonic]

holy shit the "if r in range(rows)" is clean. never seen that before.

[@amogchandrashekar8159]

Very neet! Thanks for adding! I request you to kindly solve some dp problems as well!

[@NeetCode]

I definitely wanna do some DP soon, but I also wanna cover some of the basics first. Any specific DP problems you are looking for?

[@amogchandrashekar8159]

@@NeetCode Thanks for replying :) I am a self learnt programmer, and in these weekly leetcode contests, usually I am able to solve 3/4 questions. The 4th question is always a dp problem. I am in no hurry, but please consider my request to solve the weekly contest problems! It would be helpful.

[@aaen9417]

thanks so much for this!

[@user-vc6nf5mw3x]

thank you, because of you i realised that i should use bfs instead of recursive dfs.

[@parsasedigh750]

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

[@shdnas6695]

right

[@user-id4cx1gw5f]

@NeetCode Nice solution! I was thinking about it from a DFS point of view, and recursion instead of interation. Got a question though, what's the time and space complexity of this? Thanks!

[@mahmoudelsayed6943]

I think that the time complexity is O( n x m ) as you iterate through all elements in the grid and visit them only once, and space complexity you used a queue and a set which will at most have (n x m) elements, this is an image explaining space complexity of queue in 2d grid

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

[@mehershrishtinigam5449]

No wait, how would that work?

[@mehershrishtinigam5449]

i got it btw, this is my c++ code class Solution { public: void dfs(vector& grid, int i, int j){ if(i >= grid.size() or j >= grid[0].size() or j < 0 or i < 0 or grid[i][j]=='0') return; grid[i][j] = '0'; // Marking as visited. dfs(grid, i+1, j); dfs(grid, i, j+1); dfs(grid, i-1, j); dfs(grid, i, j-1); } int numIslands(vector& grid) { int num = 0; for(int i = 0; i < grid.size(); i++){ for(int j = 0; j < grid[0].size(); j++){ if(grid[i][j] == '1'){ dfs(grid, i, j); num++; } } } return num; } };

[@aniketbhanderi5927]

But still the space complexity remains O(m*n) because of depth first search or breadth first search is involved in algorithm.

[@oogieboogie7028]

It is generally a good coding practice to not change the input data.

[@oogieboogie7028]

​@@aniketbhanderi5927 worst case time complexity of a set can be O(n) in case of collision. It's generally not the case tho.

[@nagendrabommireddi8437]

I attended one coding round .in that they asked to print all substrings ...I did that in O(n^2)...by using for loops and another using combinations but time limit exceeded ... please make a video on that please

[@asdfasyakitori8514]

Great video!

[@xxRAP13Rxx]

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()

[@charleschen3538]

Great caveat! I just learned that for DFS we set the node as visited only after it's popped out of the stack, whereas in BFS we set it as visited right when we pushed it into the queue

[@xxRAP13Rxx]

*but ALSO call visit.add(…)

[@LuminousElysium]

This is a very interesting discovery that has sparked a lot of thoughts for me. Essentially, it all comes down to how you interpret "nodes being visited." If you consider adding to `visit` as visiting the nodes, then you are correct. However, if you shift the perspective and consider performing certain operations (like outputting) as visiting the nodes, then the statement in the video is not problematic. For example: class Solution: def numIslands(self, grid: List[List[str]]) -> int: rows, cols = len(grid), len(grid[0]) will_visit = set() # call it `will_visit` instead result = 0 for row in range(rows): for col in range(cols): stack = [] if grid[row][col] == '1' and (row, col) not in will_visit: result += 1 stack.append((row, col)) will_visit.add((row, col)) while stack: r0, c0 = stack.pop() print(r0, c0) # actual visits happen here for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: r, c = r0 + dr, c0 + dc if r in range(rows) and c in range(cols) and grid[r][c] == '1' and (r, c) not in will_visit: stack.append((r, c)) will_visit.add((r, c)) return result This truly does DFS.

[@charleschen3538]

@@LuminousElysium Hmm, honestly I'm not sure if this is actually DFS? My understanding of the stack is that it represents the DFS sequence of how we process or traverse the graph. (BFS sequence is different such that we use a queue to represent it) However, for this statement "(row, col) not in will_visit", you will check whether such node is already pushed on the stack in your case since your code push the node on the stack and set it as visited at the same time. I think this might lead to a problem such that the sequence your stack represents isn't actually a DFS sequence because if one node is connected to a node we've already "seen" (pushed on the stack) before, we won't push it onto the stack again. However, the DFS sequence essentially tells us that we would traverse the path "to the very possible end", so we could potentially add duplicate node onto the stack as such path might involve a node we already "seen" before. Not sure if I'm making my idea clear but this is just my thought so far on this, please correct me if you find something wrong

[@xxRAP13Rxx]

@LuminousElysium In iterative DFS, it is best to mark a node as visited only after popping said node from the stack. Otherwise, no node can visit their uncle because their grandparent already visited the uncle.

[@feeling4929]

Good explanation.

[@ln11389]

You could use set.intersection() method instead of using double nested loops for the last part where you append the cell coordinates to the result list. It would basically be: result = [ ] for cell in atlSet.intersection(pacSet): result.append(cell) return result

[@itachid]

Yup, you could. But what if the interviewer tells you not to use library functions?

[@ln11389]

@@itachid Question him why it is useful to write own implementation of something that already exists. Why should a candidate not be allowed to use online resources and built-in library functions?

[@khagharhimerov3462]

What will be the time and space complexity? Thanks

[@ashishchoudhary1664]

I think this solution is a little complicated. This video is 3 years old so I guess Neetcode improved on the coding skills a lot as I used one of his later videos Here's the solution: class Solution: def numIslands(self, grid: List[List[str]]) -> int: res = 0 ROWS, COLS = len(grid), len(grid[0]) def backtrack(r, c): if (r < 0 or c < 0 or r == ROWS or c == COLS or grid[r][c] == '0'): return # mark this position as visited/0 grid[r][c] = '0' backtrack(r + 1, c) backtrack(r - 1, c) backtrack(r, c + 1) backtrack(r, c - 1) # visit valid land positions and its neighbors for r in range(ROWS): for c in range(COLS): if grid[r][c] == '1': backtrack(r, c) res += 1 return res

[@halcyonramirez6469]

This is one is pretty easy to do once you've done the pacific waterflow

[@siddhr6241]

Just a small optimization, you could just modify the given grid's "1" to "0" to avoid keeping a visited set.

[@lahaale5840]

Very nice video. In the BFS, should we use q.pop() instead of q.popleft()? Because q.popleft() makes the q as a stack, which is DFS, right?

[@NeetCode]

In this case, popleft will pop the cells in the order that they are added which is BFS. My understanding is that pop(), pops from the right of the queue which is similar to a stack.

[@sairamsunkara5395]

Time Complexity: O(m.n) for looping through each node looking for 1st piece of land we are costing a max of m.n for mxn grid. This is simple so far, the complex part is that for each node in the grid, we can call bfs(or dfs) which can take more complexity. But if you look at the sum of nodes that bfs(or dfs) touches is bounded by m.n. For example, if we touched k nodes in mxn grid in the first bfs(or dfs) call, then in the next call we can only touch a max of m.n-k nodes as we already marked the previous k nodes as visited and will skip them. So, we can touch m.n nodes in the loop, and a max of m.n nodes in bfs(or dfs) call making it a O(2.m.n) -> O(m.n) excluding constants

[@mayankpant5376]

Hey Neet, how are you able to navigate to different parts of code so fast like at 10:31 when you were replacing the duplicate code. Thanks!!

[@vanchark]

With his mouse. Play FPS games to get pinpoint mouse accuracy

[@garimadhanania1853]

I was asked in the Meta mock interview today. I coded a similar solution with a main with 2 for loops and helper bfs function using a queue. The feedback the interviewer gave at the end was that dfs would be better for this. For problems like shortest path - bfs is good. However, for this problem, it will be faster to go in-depth order. When I had initially mentioned bfs, he also asked me to explain how I would do it, and the time complexity. Of course, the worst-case time complexities are the same for both bfs and dfs and its O(m*n). It is hard for me to understand why dfs would be better though?

[@ikrammaududi6205]

Look at nick white video on this. He uses dfs. Dfs is better for this, since it's easier to write - it uses less logic

[@tenzinmahabir4669]

For C++ implementation, is it fine to use a 2d vector of bools to keep track of visited cells. Are is there a more efficient/better way? Thanks for all the great videos!

[@muddycalendar3292]

There actually is! You can replace each 1 with a 0 as you go over it, and that way you don't have to use any extra space

[@dj1984x]

what is the benefit to solving this with bfs instead of dfs? dfs seems easier to understand imo, maybe I just need to practice bfs more

[@DornaHa]

Thanks for the very helpful videos 🙏 We can improve the space complexity by setting the cells we visit on the grid to 0, instead of using a separate visit set.

[@sahil_tayade]

That is true! However, if this was supposed to emulate a real problem, then whoever is calling the function might not want you to change their 2d matrix. Then they would have to create a copy anyway.

[@Vitalik186]

Thank you!

[@MichaelButlerC]

I think I might try marking the cells as visited by changing the "1" to another char such as "v". maybe that's why LeetCode did it as a string instead of number. then you don't need more memory with the set pairs.

[@victoriac7257]

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?

[@TheFirzoknadeem1]

1, 1, 1 0, 1, 0 1, 1, 1

[@aulanx]

imagine a really large island with many peninsulas, where there's one part of the land attached to the island on one side only. going in all four directions will cover all the cases

[@wizardkoer782]

8:34 it doesn't really make a difference but the ith position is above and below and jth position is left and right. A good little distinction to understand when you're trying to render a 2D or 3D array in your brain and you brain GPU is maxing out.

[@asifchoudhuryca]

Wonderfully explained! Truly "neet" code. A quick question: what is the O(n) complexity?

[@tamilupk]

O(n * m)

[@picnicbros]

This problem is basically the same as Number of Connected Components in an Undirected Graph - Union Find - Leetcode 323 (also his video), and I think Union Find is easier to implement once you know the basic. But this implementation introduces you to BFS if you don't know already.

[@ordinarygg]

yes, yes how many times you solved this in your work) correct 0 times)

[@caiodavi9829]

@@ordinaryggwhy are you so mad? lol

[@Troglodyte2021]

Brilliant!

[@khappekhappe133]

if you wanna use dfs instead: if not grid: return 0 rows = len(grid) cols = len(grid[0]) count = 0 for r in range(rows): for c in range(cols): if grid[r][c] == "1": self.dfs(grid, r, c) count += 1 return count def dfs(self, grid, r, c): if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != "1": return grid[r][c] = "#" self.dfs(grid, r+1, c) self.dfs(grid, r-1, c) self.dfs(grid, r, c+1) self.dfs(grid, r, c-1)

[@felipeoriani]

The explanation on the video helps, but this solution is so simple to understand. Thanks for sharing.

[@pl5778]

A question I have here is using DFS approach. In the courses, during graph DFS, its usually paired with using a hashset to keep track of visited coordinates/nodes, and during backtrack portion we would remove it from the hashset. However, for this problem there is no need to remove it from the hashset. Why is that the case? Is it because we are expanding the search like BFS? If for a different problem, for example - 'number of ways to reach a point', the coordinates would need to be backed out from the hashset to avoid double counting?

[@orkhanbaghirli7985]

I guess that is the case for DFS for the visited node cannot be visited again during the "same path"; however, it can be visited during the another path. Here, there is no backtracking and the problem only requires not to visit the cell if it is already part of "any" island, not just the "current" island. I hope this helps.

[@stealth_chain]

you don't need the visited set if you alter the data of the list. you can mark "1" -> "2" to mean "visited".

[@vladimirstrigunov7412]

Get outta here! This is such a smooth explanation of a question that truly intimidated me before!

[@amitupadhyay6511]

Thanks for the awsome video. Could you please solve this one :694. Number of Distinct Islands

[@pruthvihingu3733]

I think the flood fill algorithm is faster than BFS or DFS approach in this problem and It also requires less memory :)

[@YakyuBoy]

You're helping so many people with these solutions. Dumb question, but why doesn't visit needed to be passed as an argument to bfs() function along with r and c?

[@johndong4754]

Late reply, but the bfs() function is declared within the given function, and the visit set is declared outside of the bfs function and in the given function, so the bfs function already has access to the visit set

[@danielsun716]

Under the description of this problem, the constrains said 1

[@sanskartiwari2496]

Yeah. While the constraint does mean that number of rows and columns will always be greater than 0, it never says there need be atleast one island in the matrix and so all elements could be water i.e 0. The above said statement takes care of a case where all elements of the matrix are 0 because python treats it as an empty matrix hence evaluated as False.

[@aishwaryaranghar3385]

the explanation is fire

[@OMFGallusernamesgone]

I like to set visited to 2 to remove the visit set, but that solution gives me a too many recursive calls error in recursive dfs, though it works in bfs

[@jaehoonie]

6:05 how did you move out of brackets here by typing on the keyboard? I just started learning vim but I don't think this is possible without exiting insert mode, but he seems to do so without changing modes.

[@matthewgand]

i see that you are a vim expert now

[@jaehoonie]

@@matthewgand LOL WTF MATT WASSUP MY GUY

[@nagendrabommireddi8437]

SIR please do a video on printing all substrings of a string in O(n)..or less than that .. please sir ..

[@nivedithabaskaran1669]

Is the time complexity O(2 N^2)?

[@elyababakova2125]

Great video! Btw we can optimize space by using grid itself to mark visited cells. Also I like a recursion solution, it looks intuitive and clean. Check this out: class Solution: def numIslands(self, grid: List[List[str]]) -> int: def isIsland(i, j): if not (0

[@MichaelButlerC]

cool yeah this was my hunch as well. the fact this problem was categorized as "graph" kind of tripped me up since I've done flood fill stuff like this before

[@caiodavi9829]

@@MichaelButlerCa grid is a special type of graph. this is why

[@wintermute1814]

In fact you can just set grid[i]j] to "0" rather than "v", and save an additional check :)

[@stefanopalmieri9201]

Modifying the input variables is generally not advised.

[@thiagot7706]

thank you, using recursion is much better. I did a similar approach: class Solution: def numIslands(self, grid: List[List[str]]) -> int: islands = 0 def dfs(i, j): if (i < 0 or i >= len(grid) or j < 0 or j >= len(grid[i]) or grid[i][j] == '0'): return grid[i][j] = '0' # do the dfs dfs(i - 1, j) # down dfs(i, j - 1) # left dfs(i, j + 1) # right dfs(i + 1, j) # up return 1 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == '1': islands += dfs(i, j) return islands

[@il5083]

Actually we can modify the items in grid "1" -> "0" to avoid using extra space.

[@s4ltokyo]

Good point. No need to use additional space

[@eddiej204]

bro Neet, could u tell the time complexity of this solution, pls?

[@prafulparashar9849]

Genius !!

[@jsboomer1917]

what is the time complexity?

[@Jon-dk4qu]

For the directions part 8:33 do u mean [1,0[] direction below, [-1,0] direction above, [0,1] direction to the right etc. I feel its the opposite logic to what u said, but please clarify? Thank You

[@halahmilksheikh]

Yeah that confused the heck out of me. It should be this way, I thought I was going crazy

[@GESAM121]

What is the time complexity of the algorithm?

[@sudharsanamtk]

What is the order of this algorithm? is it o(rowxcolum)?

[@hazelnut5458]

Can you upload some questions about heap?

[@thewelcomer5698]

Is it possible to use recursive DFS for this problem? I find that simpler to understand but I'm sure there's some tradeoffs that make BFS better.

[@vukanoa]

I implemented it using recursive DFS and it's infinitely more readable and easier to implement. It said that Time beats: 88% and Space beats: 97% I guess that's enough. Though LeetCode let's you modify "grid". If it didn't I'd just have an additional set to remember which positions I've already checked.

[@rickonzhang407]

shouldn't the conditions on ine 19-22 be separated? if r or c are out of the range, indexing grid[r][c] would give an error, which is what I encountered

[@akshatmishra6348]

simply change the order of condition . check for 'grid[r][c]=='1'' at the last position after checking " r in range(rows) and c in range(cols)".

[@edonis2787]

1,0 is below, -1,0 is above, 0,1 is right and 0,-1 is left

[@jugsma6676]

I think, i have similar but maybe simpler: def solution(grid: list[list[str]]): visited = set() island = 0 def helper(row, col): if row=len(grid[0]) or grid[row][col] != "1": return grid[row][col] = "#" helper(row, col+1) helper(row+1, col) helper(row-1, col) helper(row, col-1) for row in range(len(grid)): for col in range(len(grid[0])): if grid[row][col] == "1" and (row, col) not in visited: helper(row, col) island += 1 return island

[@jugsma6676]

def numIslands(grid: list[list[str]]) -> int: rows, cols = len(grid), len(grid[0]) visited = set() def dfs(r, c): if (r < 0 or c < 0 or (r,c) in visited or r >= rows or c >= cols or grid[r][c] == "0"): return 0 visited.add((r, c)) dfs(r+1, c) dfs(r-1, c) dfs(r, c+1) dfs(r, c-1) # visited.remove((r,c)) return 1 res = 0 for r in range(rows): for c in range(cols): if grid[r][c] == "1": res += dfs(r, c) return res

[@aumrudhlalkumartj1948]

Thanks

[@TharinduWeerasooriya]

the solution in your video is different from the solution you've included in leetcode discussion. You might want to add the annotation to KZbin.

[@ordinarygg]

"if not grid" will return true because [[]] -> is not False

[@vrybak82]

would it be worse to do this problem using DFS to mark an island instead?

[@NeetCode]

I think for this problem both DFS and BFS are about the same. It probably depends more on which one you are more comfortable with coding.

[@waynetocode5086]

The best and clear explanation

[@lilyh4573]

This was so hard X_X Neet you must be a genius if this is your favorite my brain hurts

[@seethruhead7119]

i did this for the first time last week i just "destroyed" the island as i visited it setting the visited 1's to zeros before calling destroy(nextSquare) this simplifies the code because the visited check and isIsland check become the same also i didn't use a typical dfs or bfs but i did recursively try and "destroy" islands in all 4 directions

[@theFifthMountain123]

The directions you mention is wrong. Correct way is: [1,0] is row+1 and same col; so down [-1,0] is row-1 and same col; up [0,1] is same row and col+1; down [0,-1] is same row and col-1; up

[@cici-lx6np]

Using q = deque() or q = collections.deque()? My question is that is there any difference between theses two? When shall we decide to use one instead of the other?

[@NeetCode]

I think they're the exact same,

[@cici-lx6np]

@@NeetCode Many thanks!

[@scullyy]

Using my own solution I get the right answer on 99% of the tests, but one of them I get 44/45. I have no idea how and in the input size is too large to go through step by step xD

[@abhimalyachowdhury7835]

I came here to understand the problem...Seems while explaining the first example...you skipped one 1 which is connected to the same island but is having a 0 as its neighbor...But it should be included in the same island because its vertically connected to another 1...Made me a little confused in the begining!

[@AjaSiva]

Same me too!

[@doggydoggy578]

Nice, can you show me code how to solve the number of island problem by UCS