You could absolutely do that. Although it doesn't save too much time because the hashset lookup is also O(1). Yours doesn't use hashing though which would indeed be a bit faster
@@lOmaine777 Good memory ! That was in Greg's solution to Leetcode 200 (th-cam.com/video/9dOFm8am4Qs/w-d-xo.html). Yes, an interviewer said that -- recruiters don't usually code. 🙂 In production code, input modification is a no-no. In programming contests, it's totally fine. In interviews, it's best to ask the interviewer. 👍
you can also use an [n,m] boolean array which also O(1) time for lookup and while it might take more space when there's fewer island, you do save up on hashing when you lookup and insert in the set.
I think I have an O(mn) time and space solution that doesn’t require DFS or a hashset. It involves storing the size of each island in a list (beginning with just [0]), and as you march through the list (left-to-right and up-to-down), you check the value of the cell, the of the above cell, and the value of the cell to the left. If the current cell is 0, nothing happens and it stays 0. If both above and left of the current cell is 0, set the cell to the length of the sizes list, and then append a 1 to it. If exactly one of the cells is a 0, add 1 to the element in the list with the index of the nonzero value, then set the cell’s value to the same as the nonzero cell. If both are nonzero, add the list’s element indexed above to the value indexed to the left plus one, then set the value indexed above to 0. Set the current cell’s value to that of what’s to the left. By the end this process, you get a list of the sizes of the islands, some of which are 0 because they are duplicates. The maximum size of this list is mn/2 if the grid has a checkerboard pattern. I’ll write some pseudocode in a reply.
@@chixenlegjo Unless the problem asks for constant space, most programmers value simplicity over space usage. BTW, you might like Antti Laaksonen's book, Guide to Competitive Programming -- it's quite good. Also, did you run your code ? Leetcode has an easy-to-use interface, and it's fun.
Interesting solution! Does it work though when the islands are non-convex in the 'up/left' direction? E.g. an 'n' or an 'F' shaped island. I'm not totally convinced that the index stored in grid[r][c] will be updated correctly in all cases, or if sometimes the program can hit an outdated one. I could easily believe it works, though, it's just hard to prove it to myself!
Hello, at my university to work with graphs and their algorithms we use the networkX Python library. Do you recommend it to work with these data structures? Which one do you recommend for this type of problem to solve? Greetings and thanks for the video.
![Portal 2: Ending, Credits Song [HD]](http://i.ytimg.com/vi/wYps-kGPh78/mqdefault.jpg)
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Congratulations for the video! When I get some free time, I'll send my C++ solution here
I want to say tracing coastlines could save time, but I think the conditions in which it would might be too specific to bother
You can optimize it: instead of using "visited" set, you can modify in-place the matrix. Set visited cells to '' (empty string) instead of 1.
You could absolutely do that. Although it doesn't save too much time because the hashset lookup is also O(1). Yours doesn't use hashing though which would indeed be a bit faster
Didn't some recruiter comment over here that in place modification of input is a red flag?
@@lOmaine777 Good memory ! That was in Greg's solution to Leetcode 200 (th-cam.com/video/9dOFm8am4Qs/w-d-xo.html). Yes, an interviewer said that -- recruiters don't usually code. 🙂 In production code, input modification is a no-no. In programming contests, it's totally fine. In interviews, it's best to ask the interviewer. 👍
@@lOmaine777data should be immutable but say if the data is mutable then inplace operations are much better
you can also use an [n,m] boolean array which also O(1) time for lookup and while it might take more space when there's fewer island, you do save up on hashing when you lookup and insert in the set.
I think I have an O(mn) time and space solution that doesn’t require DFS or a hashset. It involves storing the size of each island in a list (beginning with just [0]), and as you march through the list (left-to-right and up-to-down), you check the value of the cell, the of the above cell, and the value of the cell to the left. If the current cell is 0, nothing happens and it stays 0. If both above and left of the current cell is 0, set the cell to the length of the sizes list, and then append a 1 to it. If exactly one of the cells is a 0, add 1 to the element in the list with the index of the nonzero value, then set the cell’s value to the same as the nonzero cell. If both are nonzero, add the list’s element indexed above to the value indexed to the left plus one, then set the value indexed above to 0. Set the current cell’s value to that of what’s to the left. By the end this process, you get a list of the sizes of the islands, some of which are 0 because they are duplicates. The maximum size of this list is mn/2 if the grid has a checkerboard pattern. I’ll write some pseudocode in a reply.
grid[m][n] = …
sizes = [0]
ans = -1
for 0
@@chixenlegjo Unless the problem asks for constant space, most programmers value simplicity over space usage. BTW, you might like Antti Laaksonen's book, Guide to Competitive Programming -- it's quite good. Also, did you run your code ? Leetcode has an easy-to-use interface, and it's fun.
Interesting solution! Does it work though when the islands are non-convex in the 'up/left' direction? E.g. an 'n' or an 'F' shaped island. I'm not totally convinced that the index stored in grid[r][c] will be updated correctly in all cases, or if sometimes the program can hit an outdated one.
I could easily believe it works, though, it's just hard to prove it to myself!
Is it possible to do it by using Union-find for less space complexity? (not sure about comparing time complexity)
Yeah won't change the time complexity... Doesn't union find use space for the ranks and parents though?
Hello, at my university to work with graphs and their algorithms we use the networkX Python library. Do you recommend it to work with these data structures? Which one do you recommend for this type of problem to solve? Greetings and thanks for the video.
Are you sure that's not for networking? These are just normal graphs from a data structures point of view
networkX is for graph problems
If there are 2 with the largest size how does this return both of them?
The question wants the size, not the list of coordinates that make up the island. So it would be the same number either way. Great question
me: return 5;
That ain't gonna work homie (I know you know that haha)
what is the name of your drawing app?
Miro
Wave Li algotithm
But what does DSF mean?
Its suppposed to be DFS (depth first search)
@@frederikja2210 Thanks bro
Floodfill?
Sorta... But moreso in general just a search!
Reminds me of kmaps
What's a kmap?
@@GregHogg not much, what's k with you?
@@GregHoggsomething used to minimize Boolean Equations for designing digital circuits
Is this code logic also used by Minesweeper ? 😅
Sorta, yeah! When you press a key in minesweeper, it would do a dfs or bfs to expose all it can in that connected component of where you clicked :)
What application you used to run python
Oh. Here this is the leetcode environment
could you make it so you let us try to solve the question on our own before you give the answer
A lot of these problems are on LeetCode, I google them and try to solve them myself, if it doesn’t work I watch these!
As soon as you see code on the screen, hit the J key. That's the keyboard shortcut for "back up 10 seconds". Or look away from your phone ! 🙂
@@davidespinosa1910 it’s too late at that point sometomes
n^4😂
Hmm?
Mate I’m sick of seeing your videos. These sorts of videos only appear after Meta, Google, etc do massive layoffs.
Sorry to bother you with them lol
yeah unsubbed, as your answers are only mostly correct.
Is there a problem with Greg's code ? It looks fine to me.
Yeah, this one is correct though...
Yeah there's nothing wrong with this code.