Damn this was the chillest explanation I ever saw. "Won't be doing Tarjan's algo cuz I don't feel like it" 🤣🤣🤣. btw I wasn't able to code the solution completely but I am glad I was almost 70% correct.
Bro I was trying union find myself , then I ended up failing as well after I found about the 0 , 1 ,2 condition. Then I was stuck. But whats with the depressing comment.
Leetcode actually is getting mellisonant and overwhelming these days and it pan out to me that leetcode insidiously trying to jam down all beginner self-taught programmers like me by letting us solve this kind of problems.However, neetcode has helped to get over these obstacles with comprehensive solutions and explanations.
Luck is a big factor to crack big companies. recently i gave interview for uber for for senior fullstack developer and i was able to solve all problems and system design round was also good. but they rejected by saying, 1. Problem (optimal transaction like) feedback: i used int instead of BigInteger 2. cache design with TTL as expiration: feedback: I test the code using Thread.sleep to simulate the time same time i can explain we can have Time object as dependency and mock the same, still they gave same as feedback. 3. use better name (i used good name and i dont prefer to use a,b i and j as variables).
Thank you for the reassurance. It seems logical for companies to ask reasonable problems that demonstrate problem solving skills as opposed to the rarer, more advanced academic problems.
My solution was noticing there are 3 ways an island can be split: 1) Go through all the land and see if there are any land tiles to where filling them with water split the islands 2) Find the piece of land with the most water (or edge) around it and surround the rest with water. 3) Fill all the land with water Part A: If it's already split return 0 Part B: If method 1 splits the islands, then return 1 Part C: If doing method 2 doesn't just leave one piece of land left, return method 2, Part D: If doing method 2 does leave just one piece of land left, do method 3 NeetCode was saying that you have to make the realization that the maximum answer is 2, but I was able to arrive at this solution without that realization. After looking at the editorial I noticed if you ever get to part C or D the answer will always be 2 and so this method can be greatly simplified, but this method is able to work without making the realization that the maximum answer is 2.
actually we can keep track of the min connected sides of the 1s while iterating the grid and run the dfs. if its 1, then remove 1, if its 2 then remove 2.
hey, a small correction. Segment trees are fairly common in coding rounds of big tech companies like google, rubrik and sprinklr. (Atleast here in India, they ask all sorts of questions to fresh college grads.)
You don't actually need to count number of islands. You just need to check if any land exists and, if it is, check that the island area is equal to the total land area. So, only one BFS per iteration is needed.
i have a que, like what if i am not able to solve the que. what should i do l read the editorial first and then come to watch the video or vice versa ?
see the things is the hiring scene really depends on country and competition , obviously the needs and the questions asked are of varied difficulty , also luck is obviously a factor
Hi @NeetCodeIO, I just have one doubt...we are calling DFS only on nodes that are not in the visited set, so probably we can get rid of that condition inside the base case inside the DFS function? or we could remove the same check before calling DFS and let it get handled inside the DFS base case?
anyways, we could be smart about choosing the pairs, basically we can neglect pairs which are far off that would never cause a disconnect, and only consider pairs in near proximity (in 8 directions), which would boil down the number of pairs to be linearly proportional to the number of 1 cells, hence nm^2 would prevail. But @NeetCode, since you are mentioning brute force, you should also mention the point made above.
been doing leetcode for years, at this point I have even forgotten why? doesn't matter how much you practice in high stressed interview situations you are never coming up with such absurd solutions.
shouldn't counting the degree also work? the only counter example I can think of is the consecutive ones which is also given. Let me elaborate: 1. count islands and if it isn't one island then return the zero. 2. pass over the grid and store the degree of each not and its position 3. if there is only two nodes with degree one then return 2 (the example given) 4. if there is nodes with degree 1 then return 1 5. all nodes of degree 2 and up so return 2. I think this is in order of N*M and takes N*M space
Imagine a grd like this [ [1,0,1],[1,1,1],[1,0,1]. The min degree of all nodes is 2. If you were to return i.e 2 cells to delete. It would be wrong. You just have to delete the middle 1 in second row. The deletion of one cell will create two islands. I actually coded thinking with the same approach as you. But this node ( aka articulation point in Tarjan's algo) is thr weaklink.
Ewwuu, like for case of 0 deletion evaluate, for case of 1 deletion brut force, because if that fails for case 2 deletion we don't need brut force because if not 0 and not 1 then 2 can be the max so we don't need brut force in combination for 2 and more onwards, but you were not able to evaluate in the case of 1 deletion, ain't this true?
Man oh man, that sigh at the start - I really felt that. I spent so long trying to get something close to O(m·n) and even with the hints and some high level explanations in the discussion section, I still eventually gave up and settled on a very similar brute force-ish algorithm as your description here. I really appreciate you putting up these videos, it's really nice to know I'm not alone in being humbled.
Thank you so much for posting everyday
Lmao, you should add a new "ego crusher" category in your roadmap
I agree
Agreed
Definitely Yesss.
Damn this was the chillest explanation I ever saw. "Won't be doing Tarjan's algo cuz I don't feel like it" 🤣🤣🤣. btw I wasn't able to code the solution completely but I am glad I was almost 70% correct.
if you're only here for tarjan's algorithm.. i'm sorry
Dude whyyy 😢😢😢
I am only here for neetcode
Bro I was trying union find myself , then I ended up failing as well after I found about the 0 , 1 ,2 condition.
Then I was stuck. But whats with the depressing comment.
Why to code for the last case ? The answer 2 is obvious after checking 0 and 1
You should pin this comment.
Leetcode actually is getting mellisonant and overwhelming these days and it pan out to me that leetcode insidiously trying to jam down all beginner self-taught programmers like me by letting us solve this kind of problems.However, neetcode has helped to get over these obstacles with comprehensive solutions and explanations.
Honestly this looks hell simple when you taught.
Hindsight is always 20-20...
Luck is a big factor to crack big companies.
recently i gave interview for uber for for senior fullstack developer and i was able to solve all problems and system design round was also good.
but they rejected by saying,
1. Problem (optimal transaction like)
feedback: i used int instead of BigInteger
2. cache design with TTL as expiration:
feedback: I test the code using Thread.sleep to simulate the time same time i can explain we can have Time object as dependency and mock the same, still they gave same as feedback.
3. use better name (i used good name and i dont prefer to use a,b i and j as variables).
Solved it by myself after revealing hints on leetcode! Thank you neetcode for your videos!
Thank you for the reassurance. It seems logical for companies to ask reasonable problems that demonstrate problem solving skills as opposed to the rarer, more advanced academic problems.
It did humble me , correct category - Ego Crusher
My solution was noticing there are 3 ways an island can be split:
1) Go through all the land and see if there are any land tiles to where filling them with water split the islands
2) Find the piece of land with the most water (or edge) around it and surround the rest with water.
3) Fill all the land with water
Part A: If it's already split return 0
Part B: If method 1 splits the islands, then return 1
Part C: If doing method 2 doesn't just leave one piece of land left, return method 2,
Part D: If doing method 2 does leave just one piece of land left, do method 3
NeetCode was saying that you have to make the realization that the maximum answer is 2, but I was able to arrive at this solution without that realization.
After looking at the editorial I noticed if you ever get to part C or D the answer will always be 2 and so this method can be greatly simplified, but this method is able to work without making the realization that the maximum answer is 2.
4:38 thanks for the proof. Now, I'm satisfied.
step 1 : find SCC (strongly connecrted component) , if SCC == 0 || SCC > 1 : return 0;
step2 : find bridges in graph , if we have a bridge : return 1;
step3 : else return 2;
actually we can keep track of the min connected sides of the 1s while iterating the grid and run the dfs. if its 1, then remove 1, if its 2 then remove 2.
hey, a small correction. Segment trees are fairly common in coding rounds of big tech companies like google, rubrik and sprinklr. (Atleast here in India, they ask all sorts of questions to fresh college grads.)
Thank you for the daily solution
You don't actually need to count number of islands. You just need to check if any land exists and, if it is, check that the island area is equal to the total land area. So, only one BFS per iteration is needed.
i solve this on my own 🔥🔥
Last few minutes was too nostalgic. It felt like when my Math teacher used to come to class but not take lecture😂
Jokes apart thank you man.
Beautiful explanation. Thank you.
Thanks for uploading daily.
15:00
my soul is crushed
14:27 bro almost got demonetized 💀
DFS for victory :))
ego crushed, you make it so easy though, the elimination intuition made it easier, thanks alot
i have a que, like what if i am not able to solve the que.
what should i do l read the editorial first and then come to watch the video or vice versa ?
see the things is the hiring scene really depends on country and competition , obviously the needs and the questions asked are of varied difficulty , also luck is obviously a factor
The hints do mention maximum of 2 removals. It was easy enough to figure out, however the edge cases for the 1 removal were crazyyy
damn I forgot they even had hints
yeah , i have tried the brute force , it was really painful.
Hi @NeetCodeIO, I just have one doubt...we are calling DFS only on nodes that are not in the visited set, so probably we can get rid of that condition inside the base case inside the DFS function? or we could remove the same check before calling DFS and let it get handled inside the DFS base case?
Thank you so much
"I fear not the man who has practiced 10,000 kicks once, but I fear the man who has practiced one kick 10,000 times."
Bruce Lee
the TC could go nm^3 incase of the remove 2 case, because there are nC2 choices of pairs to be removed
anyways, we could be smart about choosing the pairs, basically we can neglect pairs which are far off that would never cause a disconnect, and only consider pairs in near proximity (in 8 directions), which would boil down the number of pairs to be linearly proportional to the number of 1 cells, hence nm^2 would prevail.
But @NeetCode, since you are mentioning brute force, you should also mention the point made above.
No need to check pairs.
Boom boom. Lov' it! 😂🔥
u look good with face cam while explaining pls do use it
thank you...❣
been doing leetcode for years, at this point I have even forgotten why? doesn't matter how much you practice in high stressed interview situations you are never coming up with such absurd solutions.
shouldn't counting the degree also work? the only counter example I can think of is the consecutive ones which is also given.
Let me elaborate: 1. count islands and if it isn't one island then return the zero. 2. pass over the grid and store the degree of each not and its position 3. if there is only two nodes with degree one then return 2 (the example given) 4. if there is nodes with degree 1 then return 1 5. all nodes of degree 2 and up so return 2. I think this is in order of N*M and takes N*M space
Imagine a grd like this [ [1,0,1],[1,1,1],[1,0,1]. The min degree of all nodes is 2. If you were to return i.e 2 cells to delete. It would be wrong. You just have to delete the middle 1 in second row. The deletion of one cell will create two islands.
I actually coded thinking with the same approach as you. But this node ( aka articulation point in Tarjan's algo) is thr weaklink.
0:01:00 was that a brain boom, :P
This was an absolute ego crusher for me too, jesus. I eventually got it, but at what cost?
I did it using graph today 🤔
🐐
I was getting runtime error just for not putting directions array outside the dfs function. Else I did it by myself.
Line 14 indentation error
Is this anyway related to finding the Articulation point/finding bridge in graph or something like that
yes
Ewwuu, like for case of 0 deletion evaluate, for case of 1 deletion brut force, because if that fails for case 2 deletion we don't need brut force because if not 0 and not 1 then 2 can be the max so we don't need brut force in combination for 2 and more onwards, but you were not able to evaluate in the case of 1 deletion, ain't this true?
I cant follow at all rip
Man oh man, that sigh at the start - I really felt that. I spent so long trying to get something close to O(m·n) and even with the hints and some high level explanations in the discussion section, I still eventually gave up and settled on a very similar brute force-ish algorithm as your description here.
I really appreciate you putting up these videos, it's really nice to know I'm not alone in being humbled.