ACCOUNTS MERGE | LEETCODE # 721 | PYTHON SOLUTION
Vložit
- čas přidán 13. 03. 2022
- In this video we are solving a popular Google and Facebook interview question: Accounts Merge (Leetcode 721).
This is one of my favorite problems because it's a fun graph problem that isn't immediately obviously a graph problem and requires you to modify the given input and transform it into a graph before you can actually solve the problem.
Stay tuned to find out how we're going to solve this question and make sure to subscribe to the channel! - Věda a technologie
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!
Was stuck on this problem but now I can do it. Thanks a lot. Glad I found the channel.
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!
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.
Amazing Explanation! Thank you so much!
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!
Explanation is amazing as always, just subbed!
Thanks for explaining!
This is great man!. Thank you so much.
i like your sarcastic tone in the video! Keep it up!
Great explanation! Can you also add solution to Calender I problem on leetcode. Thanks!
Thanks! Hope to see comments of the code if possible...somewhere in a github?
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.
Thanks for this. Will the interviewer be ok with this solution and not union-find?
Thanks!
thank you!
lol i love the intro about karma!!
Hehe got to get you guys to subscribe somehow!
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
Great explanation! Keep it up man
Thank you! Will do! Make sure to keep watching 😃
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
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
For the good karma!
really nice
Thanks for the kind words. Make sure to subscribe so you don’t miss future videos
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
Can it be done using union find algo?
yes
i subscribed long time ago, but I need more good karma, please send me good energy!
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'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
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
subscribed!
Welcome to the channel
One question - Why would sorting be Nlog K and not k log k
Following
Thanks for the clear explanation @crackfaang! Could you please confirm the time complexity?
lol good karma