ACCOUNTS MERGE | LEETCODE # 721 | PYTHON SOLUTION

[@Amy-nq3xw]

Your channel is such a hidden gem. I really like how you don't just solve all the mainstream LC questions but also the ones that are more advanced but useful. Thank you!!

[@aglovecraft]

This is a great explanation. I watched like 4 other videos of people explaining this problem and you're the only one who took the time to visually represent the problem. That step is so helpful in remembering the logic for these problems. Keep up the great work!

[@crackfaang]

Thanks for the kind words! Based on my channel analytics a lot of people just watch the code portions but I’m glad people are getting value from the drawing parts too. Make sure to subscribe so you don’t miss future videos!

[@谢雨潇]

Nice tutorial! I have a disagreement with the complexity calculation though. We have N accounts -> then N scattered graphs -> ForEach graph, we do traversal(K) + sorting(KlogK) = KlogK, finally O(NK logK). Ignore the nested-loop format, we still traverse every single node in one graph; after this traversal, we do one sorting. We should not have those many multiplications. Please correct me if I'm wrong.

[@th2315]

I really like the way you do a very detailed complexity analysis in the end, I learned quite a lot from that, and I don't see other users doing that much. Please keep doing so! Appreciated!

[@hulyahare7718]

I've watch a lot of videos about this question but I couldn't understand any of them. But your vido is just GREAT, I get it finally! THANK YOU SO MUCHH for showing that it's actually very easy!

[@crackfaang]

Glad you found it useful!

[@rsKayiira]

Was stuck on this problem but now I can do it. Thanks a lot. Glad I found the channel.

[@3rd_iimpact]

Thanks for this. Will the interviewer be ok with this solution and not union-find?

[@TooManyPBJs]

Great video. One thing I would nitpick is that you are visiting a node, not an edge.

[@crackfaang]

Yea I tend to mix the terminology. You get the idea though

[@annlaosun6260]

thank you. after watching so many dfs videos from you. I used a dfs function to code this question and I was able to code it. !

[@electric336]

Very good explanation. Probably the best I've seen regarding this problem.

[@portiseremacunix]

Thanks! Hope to see comments of the code if possible...somewhere in a github?

[@markthompson2813]

For the time complexity, wouldn't the sorting time for K items be K Log K? That would make the ultimate Time complexity O( N * K * N * K * Log K) -> O(N^2 K^2 Log K) ?

[@geekydanish5990]

correct

[@syafzal273]

Love your explanation! I feel like the DFS would've been more intuitive recursively instead of iteratively. (This is your code, with just using recursive DFS) class Solution: def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]: graph = collections.defaultdict(set) # map of email -> name email_to_name = {} # build a graph for account in accounts: name = account[0] for email in account[1:]: # just connect to the first email # instead of connecting each email to # every other one graph[email].add(account[1]) graph[account[1]].add(email) email_to_name[email] = name res = [] visited = set() cur = [] # return all emails connected to the email def dfs(email): if email in visited: return visited.add(email) cur.append(email) for nxt in graph[email]: dfs(nxt) for email in graph: if email not in visited: dfs(email) res.append([email_to_name[email]] + sorted(cur)) cur = [] return res

[@무야호-w8g]

if possible, can you show the recursive way to implement DFS for this question?

[@hudsonyuen]

This worked for me - not the most space efficient tho class Solution(object): def accountsMerge(self, accounts): """ :type accounts: List[List[str]] :rtype: List[List[str]] """ graph = {} emailNameMap = {} for account in accounts: name = account[0] for email in account[1:]: if email not in graph: graph[email] = set() # connect every email to the first one for efficiency # we know there will be >= 1 email, so index 1 in bounds graph[email].add(account[1]) graph[account[1]].add(email) emailNameMap[email] = name visited = set() def dfs(email, connected): for email in graph[email]: if email in visited: continue visited.add(email) connected.append(email) dfs(email, connected) return connected res = [] for email in graph: # return array of all emails connected to that email, including itself connected = dfs(email, []) # if no connected emails that are unvisited, it's already been added if len(connected) == 0: continue connected.sort() # append name to front, then append to res array res.append([emailNameMap[email]] + connected) return res

[@callmejustlenny]

i like your sarcastic tone in the video! Keep it up!

[@rachnaramkumar]

Amazing Explanation! Thank you so much!

[@fallencheeto4762]

Explanation is amazing as always, just subbed!

[@nehanarwal2944]

Great explanation! Can you also add solution to Calender I problem on leetcode. Thanks!

[@ebenezeracquah478]

This is great man!. Thank you so much.

[@akhilchandra5935]

lol i love the intro about karma!!

[@crackfaang]

Hehe got to get you guys to subscribe somehow!

[@deezeey5811]

Thanks for the solution! Btw why is this DFS not BFS?

[@crackfaang]

Doesn’t matter. You have to fully explore all paths. Both will work here though I guess when you want to fully explore a path you typically use DFS in theory but it doesn’t matter. Just personal preference here

[@bdjsjjs]

I think what he uses is BFS instead of DFS. That's my thought. Correct me if I'm wrong.

[@bdjsjjs]

Oh, it's a dfs

[@jimmyahmed5424]

Thanks for explaining!

[@preethisowjanya5203]

thank you!

[@sonalverma5981]

Can it be done using union find algo?

[@geekydanish5990]

yes

[@leetcoderafeeq2641]

Thanks!

[@nehanarwal2944]

One question - Why would sorting be Nlog K and not k log k

[@read200books]

Following

[@fadsa342]

I'm still a little confused about how he created the graph and why you only have to connect each email to the first one in the list instead of connecting each email in the list to all the others

[@crackfaang]

It's simpler to do it this way. You will still be able to traverse the entire graph by only populating that first email. If you were to populate every single possible connection bidirectionally it would drastically increase the processing time and the storage space. There's no reason to do so when only populating the first will allow you to traverse the graph with the same result. For this one I'd suggest drawing out an example on a piece of paper and going through the algorithm line by line to understand. That's what helped me when I first came across this problem

[@SeanKearney-g7d]

cool

[@AmgaaKhosbayar]

For the good karma!

[@benjaminnguyen592]

Great explanation! Keep it up man

[@crackfaang]

Thank you! Will do! Make sure to keep watching 😃

[@mateo9912]

Need the good karma

[@vigneshsampath3256]

I subscribed. Hope to get the good Karma.

[@crackfaang]

Thank you! Glad people are hearing the message. If only more people did the same haha I would have a lot more subscribers! 😀

[@NinjiaJoeLife]

really nice

[@crackfaang]

Thanks for the kind words. Make sure to subscribe so you don’t miss future videos

[@nguyentuan6108]

subscribed!

[@crackfaang]

Welcome to the channel

[@Lily-xp2vb]

i subscribed long time ago, but I need more good karma, please send me good energy!

[@sharwariphadnis1298]

Thanks for the clear explanation @crackfaang! Could you please confirm the time complexity?

[@lalalagogo8508]

lol good karma