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.
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()
please make solutions for leetcode weekly contests here onwards if possible please, your explanations are very easy and understandable. No one on TH-cam explains better than you. So I can learn to solve weekly problems
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.
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.
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()
I'm just happy that I'm able to at least understand the terminologies used in this video 😅
Wait what was the time and space complexity?
Thanks for great work!
The neatness of ur code makes u neetcode😊
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 TH-cam explains better than you.
So I can learn to solve weekly problems
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.
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
If you're looking for today's daily LC (Design Add and Search Words Data Structure) 👉th-cam.com/video/BTf05gs_8iU/w-d-xo.html
Love to you from India sir ❤️
Bro make videos on leetcode contests too
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.
@NeetCode what is the time&space complexity ?
N is length of account and m is big biggest size of emails in single list
O(NMlogNM)
This is definitely a hard problem.
Thank you
This is definitely a hard problem
Love your vids bro. Is the time complexity O(NKlogK) where N accounts, K max-emails in an account, as for the DFS solution?
oh god why am i so dumb?
This one should be hard 🤯
This one of tough af
kind request to solve weekly contest
please make solutions for leetcode weekly contests
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.
bad variable naming
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