NUMBER OF ISLANDS - Leetcode 200 - Python

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

[@smartwork7098]

Thank you for everything that you have done. You are awesome!

[@DED_Search]

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

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

[@arnabpersonal6729]

using that range might be expensive instead explicitly use 0

[@akhilraj6891]

I think so!

[@mixtli1975]

correct. Having to check whether r+dr is in range is O(n) because it has to check it against every element of the array. Just checking the bounds is O(1)

[@alikolenovic2503]

@@mixtli1975 if r in range(rows): # do something Time Complexity: This operation is 𝑂(1) O(1). This is because range objects in Python are implemented in a way that supports fast membership testing. When you check r in range(rows), Python checks if r falls within the start and stop bounds of the range without iterating through each element.

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

[@EngineeringComplained]

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

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

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

[@issamjm3343]

That very cool and easier solution

[@tumarisyalqun7327]

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

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

[@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! :)

[@rogdex24]

Neetcode is the reason leetcoding feels like therapy

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

[@shelllu6888]

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

[@NeetCode]

Happy it was helpful! 🙂

[@ianpan0102]

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

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

[@parsasedigh750]

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

[@shdnas6695]

right

[@shivaranjinimithun]

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

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

[@sauravdeb8236]

Hats off to the best explanation out there.

[@ram-s-77]

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

[@rvarun7777]

Much simpler: Check all 4 sides for land and set the visited node to 0 class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == "1": self.dfs(grid, i, j) count += 1 return count def dfs(self, grid, i, j): if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != "1": return grid[i][j] = "0" self.dfs(grid, i + 1, j) self.dfs(grid, i - 1, j) self.dfs(grid, i, j + 1) self.dfs(grid, i, j - 1)

[@Deschuttes]

I ain't readin all that fam

[@dumdumbringgumgum2940]

this gives an error, solution class has no attribute dfs

[@shravanne902]

Thanks!

[@NeetCode]

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

[@spiceybyte]

I like the recursive dfs search better. Thanks!

[@xmnemonic]

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

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

[@thiagosdev]

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

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

[@deepaksurya2078]

There is a typo in the solution in neetcode, the function is named as dis instead of bfs. It is a small typo, but beginners might be mistaken.

[@wkwk2o384ur]

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.

[@levizwannah]

Thank you very much. This taught me a lot. But at the beginning where you asked "How will a kid solve this problem?", if that's how the kid starts, then that kid is a genius.

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

[@il5083]

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

[@siddhr6241]

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

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

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

[@Flekks]

It works better. Neet code solutions do not works anymore.

[@bob_jones]

Nice! A few things: 1) The checks for r in range(rows) and c in range(cols) are pretty inefficient even if pretty. I'd recommend using normal boundary checks. 2) If you can destructively change the input, you can replace 1s with 0s in the bfs and not worry about another visit occurring, which removes the need for a visit set.

[@jx7433]

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

[@djmeredith6520]

Beautiful clean solution and well explained. Thank you!

[@KaunteyaPatil]

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

[@ayushijain3340]

Well done nicely explained :-)

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

[@AnkitYadav-cw8oo]

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

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

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

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

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

[@vladimirstrigunov7412]

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

[@kashishkavi8416]

It works, But honestly found it to be very complicated the way you wrote the code. I watched Greg Hogg's solution for this problem, that was much easier Marking "Visited" in the grid itself is much easier. But Thanks for the other solutions, you are doing great!

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

[@halcyonramirez6469]

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

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

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

[@edonis2787]

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

[@CostaKazistov]

BFS is nice and all, but no longer works for this particular problem. Try testing this grid: 1 1 1 0 1 0 1 1 1 Should get 1, but instead getting 2 in results. Looks like LeetCode have updated tests, so above solution is no longer valid. Spent a good hour and half trying to figure out why BFS has been invalidated. DFS approach seems to be the way to go.

[@shreyanshgoyal8246]

yeah even I am wondering why it doesn't work anymore

[@Nick-qy7lk]

I tried this problem with bfs and realized I was getting the wrong solution because I was checking if (row/col - 1 > 0) instead of (row/col - 1 >= 0). If you make the mistake I did it completely skips the bottom left cell (2,0) because when the cell (2,1) checks for neighbors, the value of (col - 1) is equal to 0 and because our condition is strictly greater than 0 it doesn't add that cell to the queue.

[@shayshay8295]

You don’t need a queue, you can make the visited nodes as minus.

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

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

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

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

[@PhanNghia-fk5rv]

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

[@khagharhimerov3462]

What will be the time and space complexity? Thanks

[@ordinarygg]

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

[@akhma102]

Brilliant Explanation!

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

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

[@sarveshs1118]

This code will help with space complexity by 90%... def numberofislands(grid): if not grid: return 0 rows=len(grid) cols=len(grid[0]) islands=0 def bfs(grid,r,c): q=[] q.append((r,c)) while q: dr,dc=q.pop(0) directions=[[1,0],[-1,0],[0,-1],[0,1]] for roww,coll in directions: r=dr+roww c=dc+coll if ( r in range(rows) and c in range(cols) and grid[r][c]==1 ): q.append((r,c)) grid[r][c]=0 for r in range(rows): for c in range(cols): if grid[r][c]==1: bfs(grid,r,c) islands+=1 return islands

[@akhiladevangamath1277]

class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 count=0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': self.recursion(grid, i, j) count+=1 return count def recursion(self, grid, i, j): if i len(grid[0])-1 or grid[i][j]!='1': return grid[i][j] = '0' self.recursion(grid, i-1, j) self.recursion(grid, i+1, j) self.recursion(grid, i, j+1) self.recursion(grid, i, j-1)

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

[@ronhu744]

Super simple solution: class Solution: def numIslands(self, grid: List[List[str]]) -> int: y_range = len(grid) x_range = len(grid[0]) def fill(x,y): nonlocal grid if x >= x_range or x < 0 or y >= y_range or y < 0 or grid[y][x] == '0': return grid[y][x] = '0' fill(x+1,y) fill(x-1,y) fill(x,y+1) fill(x,y-1) res = 0 for y in range(y_range): for x in range(x_range): if grid[y][x] == '1': res+=1 fill(x,y) return res

[@xiaolonghui1]

Nice explanation on the thought path! Thank you1

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

[@augustoferreira238]

This video helped me a lot. Thanks for that!

[@NeetCode]

Glad it helped!

[@WaldoTheWombat]

class Solution: def map_island(self, i, j): if self.grid[i][j] == "1": self.grid[i][j] = "mapped" if i-1 > -1: # up self.map_island(i-1, j) if j+1 < len(self.grid[i]): # right self.map_island(i, j+1) if i+1 < len(self.grid): # down self.map_island(i+1, j) if j-1 > -1: # left self.map_island(i, j-1) def numIslands(self, grid: List[List[str]]) -> int: self.grid = grid count = 0 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == "1": count += 1 self.map_island(i, j) return count

[@pruthvihingu3733]

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

[@VishnuVardhan-gr6op]

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

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

[@jayasingh3515]

Only 12 out of 49 test cases are getting passed. :(

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

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

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

[@LeonardoAndradeSantana]

Really nice explanation. Thanks man

[@Mamtagoyal27]

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

[@willschab9414]

Instead of creating a set of visited coordinates you could change each 1 to a 0 after verifying it's a valid spot of land. Saves space and time.

[@yinglll7411]

Such a beautiful explanation! Thank you!

[@rishikaverma9846]

absolutely love this channel

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

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

[@abdallaobaid8474]

class Solution: def numIslands(self, grid: List[List[str]]) -> int: rows, cols = len(grid), len(grid[0]) islands = 0 def bfs(i, g): if g - 1 in range(cols) and grid[i][g - 1] == '1': grid[i][g - 1] = '*' bfs(i, g - 1) if g + 1 in range(cols) and grid[i][g + 1] == '1': grid[i][g + 1] = '*' bfs(i, g + 1) if i - 1 in range(rows) and grid[i - 1][g] == '1': grid[i - 1][g] = '*' bfs(i - 1, g) if i + 1 in range(rows) and grid[i + 1][g] == '1': grid[i + 1][g] = '*' bfs(i + 1, g) for i in range(rows): for j in range(cols): if grid[i][j] == '1': grid[i][j] = '*' bfs(i, j) islands += 1 return islands

[@amitupadhyay6511]

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

[@asifchoudhuryca]

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

[@tamilupk]

O(n * m)

[@nivedithabaskaran1669]

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

[@nagendrabommireddi8437]

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

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

[@Historyiswatching]

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

[@eddiej204]

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

[@vcoski]

I failed to answer this question at my Google interview yesterday 😅

[@asdfasyakitori8514]

Great video!

[@Vitalik186]

Thank you!

[@kafychannel]

great work thanks so much

[@aaen9417]

thanks so much for this!

[@abhaychandavar1766]

How about we just mark the visited land in the grid itself, and while traversing if we reach a visited land or if it is water then skip computation, in js I would write it this way: (I'm marking visited land with "2") var numIslands = function(grid) { const traverse = (i, j) => { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === "0" || grid[i][j] === "2") return; grid[i][j] = "2"; traverse(i + 1, j); traverse(i - 1, j); traverse(i, j + 1); traverse(i, j - 1); } let numberOfIslands = 0; for (let i = 0; i < grid.length; i += 1) { for (let j = 0; j < grid[0].length; j += 1) { if (grid[i][j] === "2" || grid[i][j] === "0") continue; traverse(i, j); numberOfIslands += 1; } } return numberOfIslands; };