It's a common Big N interview question, so it's a demoted Hard. Great if you're interested in those companies, awful otherwise, should probably be the final problem in the Union-Find section of the neetcode advanced structures course either way.
Interesting solution to use the account index as the nodes being joined in the graph. I too used a Union-Find solution but used the email strings as the nodes instead. Using the index, it is pretty trivial to find the name. In my solution, I needed a map from parent -> name. Part of the problem is that Union-Find provides as output a non-useful child -> parent tree, which you need to invert into parent -> children. The last loop can be done using list comprehension in one line.
please make solutions for leetcode weekly contests here onwards if possible please, your explanations are very easy and understandable. No one on UA-cam explains better than you. So I can learn to solve weekly problems
its O(1) given the combined optimizations of path compression in find() + the maintaining of a somewhat balanced tree he's doing using the multiple 'if' statements in union()
Cann't we just use DFS instead of using disjoint sets. ? Whats the efficiency in using disjoint sets, anyways we have to traverse all connected components.
Hi man! Move your content and thank you very much for helping us! Would love if u could also make playlists here of "Easy" , "Medium" and "Hard" related to how the leetcode problems solved in the videos are.
The path compression of find() in your code is not actually compressing path, here is the one that actually compress: def find(self, node): # Path Compression parentIdx = self.parents[node] while parentIdx != self.parents[parentIdx]: parentIdx = self.parents[parentIdx] self.parents[node] = parentIdx return parentIdx
it is compressing path. It's partial path compression. It basically updates every 2nd element to points to its grandparent. So thereby halving the path to the root parent essentially. It's kinda good because it achieves compression but not as aggressively as full path compression, thus the number of write operations is not as many when calling find(), therefore in some cases it can be more efficient when u call find
Definitely not a medium problem. Should be a hard problem in my opinion...
It's a common Big N interview question, so it's a demoted Hard. Great if you're interested in those companies, awful otherwise, should probably be the final problem in the Union-Find section of the neetcode advanced structures course either way.
The neatness of ur code makes u neetcode😊
Interesting solution to use the account index as the nodes being joined in the graph.
I too used a Union-Find solution but used the email strings as the nodes instead. Using the index, it is pretty trivial to find the name. In my solution, I needed a map from parent -> name.
Part of the problem is that Union-Find provides as output a non-useful child -> parent tree, which you need to invert into parent -> children.
The last loop can be done using list comprehension in one line.
I'm just happy that I'm able to at least understand the terminologies used in this video 😅
What a coincidence, I was working on this one. Are you doing grind75 problems now??
please make solutions for leetcode weekly contests here onwards if possible please, your explanations are very easy and understandable. No one on UA-cam explains better than you.
So I can learn to solve weekly problems
Wait what was the time and space complexity?
It would be better if u link ur union find explanation video in description itself very hectic to find that in ur old library😢
Did you find it? Im looking for it also
10:52 I don't understand how union find operations take only constant time? Worst case would be log n isn't it?
With path compression in the find() operation, it takes O(1) time is what he meant to say I guess, though I am not too sure.
its O(1) given the combined optimizations of path compression in find() + the maintaining of a somewhat balanced tree he's doing using the multiple 'if' statements in union()
Solved this problem like 3 days ago. It was a pain in the butt to get my head around using dfs with two different references.
If you're looking for today's daily LC (Design Add and Search Words Data Structure) 👉ua-cam.com/video/BTf05gs_8iU/v-deo.html
Bro make videos on leetcode contests too
Love to you from India sir ❤️
Cann't we just use DFS instead of using disjoint sets. ? Whats the efficiency in using disjoint sets, anyways we have to traverse all connected components.
Hi man! Move your content and thank you very much for helping us! Would love if u could also make playlists here of "Easy" , "Medium" and "Hard" related to how the leetcode problems solved in the videos are.
Love your vids bro. Is the time complexity O(NKlogK) where N accounts, K max-emails in an account, as for the DFS solution?
Thank you
Thanks for great work!
please make solutions for leetcode weekly contests
kind request to solve weekly contest
bad variable naming
This one should be hard 🤯
This one of tough af
first
mEdiUm...
The path compression of find() in your code is not actually compressing path, here is the one that actually compress:
def find(self, node):
# Path Compression
parentIdx = self.parents[node]
while parentIdx != self.parents[parentIdx]:
parentIdx = self.parents[parentIdx]
self.parents[node] = parentIdx
return parentIdx
it is compressing path. It's partial path compression. It basically updates every 2nd element to points to its grandparent. So thereby halving the path to the root parent essentially. It's kinda good because it achieves compression but not as aggressively as full path compression, thus the number of write operations is not as many when calling find(), therefore in some cases it can be more efficient when u call find