This is our solution and implementation to problem #1101: The Earliest Moment When Everyone Become Friends on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: The Earliest Moment When Everyone Become Friends on LeetCode.
Problem Analysis
We need to track friendships through a group of n people. At certain points in time, two people become friends, and when this happens, we can consider everybody in both friend groups to now be friends with each other (the problem lists them as aquaintances but it is simpler to consider it in this manner).
There are multiple ways of modeling these relationships. When I first solved this problem, I modeled it using a mapping between each nth person, and a set of everybody they are friends with. When people became friends, the two sets would merge, and the mapping for those two people would be updated to point to the new same set. This way solved the problem, but it isn't the most efficient solution.
There is a less-common data structure called the Disjoint Union structure. This models relationships between items, or in this case, integers. As we receive logs, we can register relationships between friends, and the data structure will automatically join the sets of friends together.
Implementation Strategy
We'll implement the disjoint union data structure itself, only with the operations we need for this problem. This will keep track of the maximum union size.
After, in the main solution class, we'll first sort the logs to ensure they are in chronological order. Then, for each log, we'll register the "union" of the two individuals and check the maximum union size. If it is equal to the number of people, we'll return that timestamp.
Space and Time Complexity
The time complexity is O(n log n). The set union operation is O(a(n)), where a(n) is the inverse ackermann function, an incredibly slow-growing function that is practically constant time. This is eclipsed by the O(n) that it takes to traverse the logs and the O(n log n) it takes to sort the logs. The space complexity is O(n).
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Solution.java file contains the main logic for the solution. Other files are used as utilities to support the main implementation.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.