Accounts Merge - Leetcode 721 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/account...
0:00 - Read the problem
0:50 - Drawing Explanation
10:10 - Coding Explanation
leetcode 721
#neetcode #leetcode #python

[@guilhermezardo7671]

Definitely not a medium problem. Should be a hard problem in my opinion...

[@christendombaffler]

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.

[@krishnasharma657]

The neatness of ur code makes u neetcode😊

[@DavidDLee]

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.

[@atreides4911]

What a coincidence, I was working on this one. Are you doing grind75 problems now??

[@technophile_]

I'm just happy that I'm able to at least understand the terminologies used in this video 😅

[@NeetCodeIO]

If you're looking for today's daily LC (Design Add and Search Words Data Structure) 👉czcams.com/video/BTf05gs_8iU/video.html

[@huzayfasabri9691]

Wait what was the time and space complexity?

[@anishkarthik4309]

please make solutions for leetcode weekly contests here onwards if possible please, your explanations are very easy and understandable. No one on CZcams explains better than you.
So I can learn to solve weekly problems

[@kyoungjunhan1098]

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.

[@pacomarmolejo3492]

Love your vids bro. Is the time complexity O(NKlogK) where N accounts, K max-emails in an account, as for the DFS solution?

[@sethusona7401]

Love to you from India sir ❤️

[@AmolGautam]

Thank you

[@dmitriytereshchenko2032]

Thanks for great work!

[@sumitsharma6738]

Bro make videos on leetcode contests too

[@subikeshps2289]

10:52 I don't understand how union find operations take only constant time? Worst case would be log n isn't it?

[@vijethkashyap151]

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.

[@hb-fm1oe]

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()

[@devenderbhatt421]

It would be better if u link ur union find explanation video in description itself very hectic to find that in ur old library😢

[@gauravdesale47]

This one of tough af

[@Daniel-do2mh]

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.

[@SHAZIALI-gw8bh]

This one should be hard 🤯

[@ranjithragul]

kind request to solve weekly contest

[@subhaspaul495]

please make solutions for leetcode weekly contests

[@ayushbhardwaj6783]

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.

[@vidur_7]

first

[@tsunghan_yu]

bad variable naming

[@Hope0fHumanity]

mEdiUm...

[@aydenwu900]

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

[@chrisdafa]

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