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!!
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!
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!
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!
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!
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.
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
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) ?
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
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
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
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
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!!
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!
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!
0:22 bro casually fear mongered me into subscribing, it was effective!
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!
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!
Glad you found it useful!
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.
Was stuck on this problem but now I can do it. Thanks a lot. Glad I found the channel.
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. !
Very good explanation. Probably the best I've seen regarding this problem.
i like your sarcastic tone in the video! Keep it up!
Love this explanation !!!!
Explanation is amazing as always, just subbed!
Amazing Explanation! Thank you so much!
Thanks for this. Will the interviewer be ok with this solution and not union-find?
Great video. One thing I would nitpick is that you are visiting a node, not an edge.
Yea I tend to mix the terminology. You get the idea though
This is great man!. Thank you so much.
lol i love the intro about karma!!
Hehe got to get you guys to subscribe somehow!
Thanks! Hope to see comments of the code if possible...somewhere in a github?
if possible, can you show the recursive way to implement DFS for this question?
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
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) ?
correct
Thanks for explaining!
Thanks for the solution! Btw why is this DFS not BFS?
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
I think what he uses is BFS instead of DFS. That's my thought. Correct me if I'm wrong.
Oh, it's a dfs
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
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
Great explanation! Keep it up man
Thank you! Will do! Make sure to keep watching 😃
Great explanation! Can you also add solution to Calender I problem on leetcode. Thanks!
Can it be done using union find algo?
yes
One question - Why would sorting be Nlog K and not k log k
Following
I subscribed. Hope to get the good Karma.
Thank you! Glad people are hearing the message. If only more people did the same haha I would have a lot more subscribers! 😀
i subscribed long time ago, but I need more good karma, please send me good energy!
thank you!
Thanks!
subscribed!
Welcome to the channel
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
really nice
Thanks for the kind words. Make sure to subscribe so you don’t miss future videos
For the good karma!
Need the good karma
cool
Thanks for the clear explanation @crackfaang! Could you please confirm the time complexity?
lol good karma