LeetCode 721. Accounts Merge [Coding Interview Solution Explained]

In this video I explain the solution of a Facebook coding interview question “Accounts Merge” [LeetCode 721].
You can find it here -
leetcode.com/problems/account...
This question is frequently asked in Google and Facebook software engineering interviews (according to LeetCode)
The code for this solution is here -
If there is a coding interview problem you would like me to cover, let me know in the comments.

[@austin4855]

I was doing well on the Grind75 list until this problem just crushed my confidence. I don't think I've ever used union find and wouldn't have recognized it, and the graph approach I was attempting had me going in circles. Thanks for the excellent explanation!

[@ShiranAfergan]

Yes union find is not super common but it does come up every now and then :) I’m glad the video helped!

[@MrMakemusicmike]

This video really helped me with this Leetcode problem.
I probably didn't code exactly the way you did, but I have a solution beating 61.97% of submissions and better than 93.09% of solutions in memory usage.
I think using lambda helped a lot for removing duplicates in the accounts that did not need to be merged.
Thanks a ton!

[@ShiranAfergan]

That’s awesome:) glad it helped!

[@harshranjankumar964]

The explanation I was looking for!!!! ❤️❤️

[@ShiranAfergan]

😊🎉

[@SumitKumar-fn3gj]

Thank you very much for this video. You teach very well. I have a hard time solving this but your way of teaching makes me understand very well and I solve it my own without seeing code of yours. Again thank you very much.

[@ShiranAfergan]

That’s awesome! I’m glad it helped! :)

[@ritwik121]

Great explanation. Thanks

[@its_chirantan]

I was struggling a lot with this problem. Thanks for the explanation.

[@ShiranAfergan]

You’re welcome. I’m glad it helped:)

[@anshumansinghrajawat7242]

Nice explanation Shiran, now i am feeling more confident in DSU, thanks!

[@ShiranAfergan]

That’s awesome 👏🏼 👏🏼 glad it helped :)

[@SeemantAggarwal]

Good explanation. It'll be more helpful if you could add comments to your code. Thanks for the great effort though.

[@lgodlike2324]

Valuable video ! Thank you very much !

[@akashjain5931]

Very well explained ! You earned a subscriber. Cheers!

[@ShiranAfergan]

Thanks :)

[@akashjaiswal6478]

The way you write code is amazing, please upload a video on what to keep in mind before writing a code and how to write an efficient code like you

[@ShiranAfergan]

This type of video is definitely on my list :) thanks 😊

[@aditisrivastava6499]

Very well explained. Thanks a lot.

[@tntcaptain9]

Thanks for the solution. One point is that if you use ordered map for email2AccountIdx, you wouldn't need to sort the vector in the end.

[@ShiranAfergan]

You’re right :) You could do that. Then the first loop will take longer because insert to map is log(n) vs insert to hash table which is average constant. But you’re avoiding the sort in the end. Complexity will be the same but if there are many duplicate emails, it will probably be better to use hash and sort at the end. Because you’re sorting less elements than what you insert to the table. What do you think?

[@sakshamkapoor5905]

Amazing explanation, thanks!

[@ShiranAfergan]

Thanks :) I’m glad it helped

[@lmnefg121]

I just looooove your lecture~!

[@ShiranAfergan]

Thanks 😊

[@andriidanylov9453]

Impressive. Thanks

[@musicperson94z]

Great video. Can you also make a video on how you learn all the algorithms or prepare interview questions in general?

[@ShiranAfergan]

Thanks Jiadong! That’s a good idea, I’ll try to think on this type of video

[@saiashok28]

@@ShiranAfergan I am searching for the same in your play list too. I like the Data Structure. Would be also helpful if you do one Data Structure with simple examples programmatically. I know too much, but would help even beginners.

[@jlecampana]

Hello Shiran Nice video. It's still such a contrived solution for this problem, it feels like without having seen the problem before you would naturally go for some kind of DFS approach though.

[@ShiranAfergan]

I see what you mean, and you could do dfs here. The complexity will be similar so it’s still a good solution but in practice it will be slower because you would have to construct the graph

[@jlecampana]

@@ShiranAfergan Thank you for your reply Shiran! I have noticed that Union-Find it's a such a prevalent topic for interviews (or at least in coding practice platforms like LeetCode it is), but do you know if Union-Find is common enough so that a Question that REQUIRES it pops up in a FAANG interview? I'm not sure if I should invest my time in learning it fully is worth it? or I could do well with Graph traversals alone. What do you think? Also, I'd be glad to be able to connect with you on Linkedin, hope it's possible. Take care and thank you for these awesome videos, keep it up!

[@jlecampana]

@@ShiranAfergan You're really great at explaining tough Interview Questions, Would you mind doing LeetCode 809 - Expressive Words next? That one is trickier than it looks IMHO and Google asks it during interviews. Have a nice week!

[@ShiranAfergan]

I don’t think union-find should be your top priority. Graphs are more important. But I would at least learn the basics of it - which operations it can do, what’s the time complexity and basic implementation.
Sure, we can connect on LinkedIn, send me an invite.
Thanks for the suggestion (LeetCode 809) I will look into this :)

[@jlecampana]

@@ShiranAfergan Just sent you a Linkedin connection request, I hadn't seen that you said I could do it, Thank you Shiran!

[@gabrieldjebbar7098]

Nice video Shiran :) You can also solve this using a graph with dfs (it's easier when you have forgotten how dsu works exactly 😂)

[@ShiranAfergan]

Thanks Gabriel, good point! I also talked about it in the video but removed it cause it was too long 😄 i was saying that DFS will take longer because you have to construct the graph but will have similar complexity so it’s also a good solution

[@gabrieldjebbar7098]

@@ShiranAfergan Hi Shiran, you should check out this question : "Find Median from Data Stream". The solution is very interesting, also it seems to be a popular interview question this days :)

[@tonystarc9567]

Great. Could you please make some more videos on problems related to union find . Any problem on leetcode that would be good to grasp the concept better.

[@ShiranAfergan]

I have another union-find problem on my channel. check out “most stones removed with same row or column”
czcams.com/video/beOCN7G4h-M/video.html

[@satyajitmahunta7906]

Simply Awesome :)

[@ShiranAfergan]

😊

[@journeytowardslife9830]

Amazing !

[@ShiranAfergan]

Thanks:)

[@akbar55555shaikh]

Can you please create video on union-find data structure?

[@kuangyimeng8850]

good video! Help me a lot!

[@ShiranAfergan]

☺️☺️

[@morzamir5197]

Genius!!

[@ShiranAfergan]

Thanks Mor 😊

[@kshitijdubey8994]

thanks :)

[@KeimaTFT]

nice video! could i ask what tool you are using to draw on your screen?

[@ShiranAfergan]

Thanks :) it’s an ipad pro and the app is GoodNotes

[@henz103]

This problem is very implementation heavy

[@arnabkhan95]

Thanks for the solution, Could you please make a video on 552. Student Attendance Record II problem?

[@ShiranAfergan]

Thanks for the suggestion! I’ll look into it

[@protyaybanerjee5051]

Can you share your screen writing setup ? Looks great

[@ShiranAfergan]

Thanks :) It’s an iPad Pro and the app is GoodNotes

[@himanshushekhar5875]

Thanks

[@ShiranAfergan]

:)

[@vanshsehgal3330]

"After a million compilation errors" - Yeah totally relatable. Damn!!😂😂

[@ShiranAfergan]

😆😆

[@shanthureddy4234]

c++ ? I wish it was in Java or C#
but thanks for the preface it is amazing and clear

[@ShiranAfergan]

Haha Cpp is my favorite language 🤓. Glad you liked the non coding parts 😆

[@RahulSingh-vv9jj]

I am new to coding can you explain line no 6 , UnionFind(int n): groupcount(n){ /code here}, I didn't understand the ->:groupcount(n) , how we are using constructor.

[@ShiranAfergan]

Hey Rahul, this line initializes the groupCount variable to n.

[@saisidharthpatlolla3542]

May I know why you are storing input in the address variables first?

[@ShiranAfergan]

Hey Sai, which address variables? Which line of code are you referring to specifically?

[@prudhvipadala3603]

UnionFind(int n):groupCount(n) {} can any please explain what this part signifies?
i know constructors but i dont understand why colon and groupCount variable given after constructor

[@ShiranAfergan]

This type of syntax is used to initialize the data members of a class. That specific line initializes “groupCount” to n. You can look up “CPP Initializer List” for more information.

[@prudhvipadala3603]

@@ShiranAfergan oh ok thank you so much

[@nipunshah1373]

Why you are not updating rank when either of merging group has lesser rank ?

[@akashjaiswal6478]

Please make a video on cheapest flight within k stops

[@ShiranAfergan]

Thanks for the suggestion! I’ll look into it :)

[@yashs6586]

Code for the solution?

[@yash.dwivedi]

which software do you use to write on the screen?

[@ShiranAfergan]

It’s GoodNotes on an IPad pro

[@yash.dwivedi]

@@ShiranAfergan Thank you for the answer

[@tombrady7390]

Leetcode 862 shortest subarray with sum atleast K if u get time please make video on it

[@ShiranAfergan]

Thanks I’ll take a look :)

[@Sksahu_123]

vgood

[@ShiranAfergan]

Thanks 🙏🏽

[@RahulKashyap-yv5ox]

Leetcode 1631
Path With Minimum Effort:Mam can you make video on this question .

[@keerthivasan138]

Mam kindly do leetcode 862

[@prashantsahu6212]

Indians are everywhere

[@uptonogood300]

this problem should be labeled hard ffs

[@AyushRaj-pm1dz]

Same C++ Code :
class UnionFind{
private:
vector parent;
vector ranks;
public:
int groupCount;
UnionFind(int n){
groupCount = n;
parent.resize(n);
ranks.resize(n);
}
void intialize(int x){
parent[x] = x;
}
int find(int x){
if(x!=parent[x])
parent[x] = find(parent[x]);
return parent[x];
}
void unify(int x,int y){
int rootX = find(x);
int rootY = find(y);
if(rootX==rootY) return;
groupCount--;
if(ranks[rootX]>ranks[rootY])
parent[rootY] = rootX;
else{
parent[rootX] = rootY;
if(ranks[rootX]==ranks[rootY])
ranks[rootY]++;
}
}
};
class Solution {
public:
vector accountsMerge(vector& accounts) {
int n = accounts.size();
UnionFind uf(n);

unordered_map mail2accountIdx;
for(int i=0;isecond].push_back(email);
}
}

for(int i=0;i

[@annsway]

Hi, Thank you for your answer. I was wondering if someone could help me debug my Java answer here: it can pass most of the test cases, but there's TLE for one test case... here's the link: docs.google.com/document/d/1NIKXhPHbNZd4YXzr9AqRXF5SpRL5v3Nnkn_M7NJNjZY/edit?usp=sharing