THE EARLIEST MOMENT WHEN EVERYONE BECOMES FRIENDS | LEETCODE 1101 | PYTHON GRAPH SOLUTION

[@dakshkant3523]

I came up with a Disjoint Set approach where initially, we assume people to not be friends with anyone. As we go through our logs in sorted order, we assign friends by changing the parents as we do in a DSU data structure. If at any point we come across a log containing people who already are friends, then we can just simply discard that timestamp as we already have a better time for them since we went through the log in sorted order of time. If they aren't friends, then we update the time. At last if there is more than 1 component in the supposed "graph", then we return -1. Otherwise we return the time we stored.

[@AcidLite]

I am a little confused, doesn't Union force 2 sets to become 1 set? If so, how can there be a case where it returns -1? I might need an example test case of it not working.

[@aishwariyaaish8305]

2421. Number of Good Paths Google question :) Though understood the solution u can give the best explanation that can be etched in our mind clearly :)

[@MinhNguyen-lz1pg]

Good explaination, Union Find is another good approach for sure, the timestamp in this problem is outrageous tho haha

[@crackfaang]

True I think union find is generally the preferred solution here but honestly I like mine because you don’t need to know union find and just some basic concepts of graphs will get you through. And luckily it’s relatively intuitive and doesn’t require you to learn a new graph algo

[@rsKayiira]

Great video. LC Diagonal Traverse II and Friends of Appropriate ages please!

[@crackfaang]

No Meta questions for a while. They are on serious hiring freeze right now, people won’t watch the videos. Need to prioritize videos to grow the channel and most people want Google questions

[@rsKayiira]

@@crackfaang understood. I'm still watching these as well. I wonder though how useful Google's top frequent questions are. I have heard people doing Google's top 200 and say it helped them tremendously.

[@IesfioI]

defaultdict isn't actually needed here right? As you're explicitly setting what the value for each needed key is

[@sharathkumar8338]

Hi Now even amazon is layingoff. 😥 Do you think these tech companies will start hiring once recession is done?

[@crackfaang]

Yea, every company will hire again in the new year. They'll need to weather the storm temporarily but they will always need talent

[@sharathkumar8338]

@@crackfaang Thank you i'll keep practicing.

[@YT.Nikolay]

New video, whoop whoop!!

[@crackfaang]

Always such a positive member of the community! Really appreciate having you here and hope you're progressing well with the prep

[@SmoothCode]

My problem with your code is that you use libraries. Google does not allow for any imported libraries during the technical interview. I can vouch that is what I heard from my recruiter.

[@crackfaang]

Defaultdict is not an imported library, it’s part of the Python standard library and is available to everyone. Plus defaultdictionary is just syntactic sugar to avoid checking the existence of a key. You could always use a standard dictionary and write the few extra lines of code. Also most recruiters are lets be honest stupid and don’t know a damn thing about coding. They usually talk out of their ass and many times as long as you can explain the data structure you are using, interviewers are fine. For example there’s many data structures in languages like Java or C++ that don’t exist in Python and make some questions they ask basically impossible to solve without a 3rd party library.

[@SmoothCode]

@@crackfaang Fair point.

[@Ahmedmeshref12]

Shouldn't space complexity here be O(M + N**2) as for every friend we keep track of at max N friends in the set?