Link to the description of the task: https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

## Straightforward Solution:

**Time Complexity** **Analysis**:

List.Add(newFriend) -> O(1) if Count is less than Capacity, otherwise O(k) where k is Count

List.AddRange(anotherList) -> O(l) if Capacity is less than Count plus l, otherwise O(Count + l) where l is anotherList.Count

List.Contains(member) -> O(k) where k is Count

Loop:

- Take a record from the log
- Get groups ids for each member {List.Contains(member)} -> 2 * O(n)
- If the ids are the same then do nothing
- If one of the ids is null then add the member {List.Add(newFriend) -> O(1) or O(k)
- If both are null then create new Group {new List{a, b}} -> O(2)
- If not null and different then merge groups {List.AddRange} -> O(l)
- If the base List.Count is 1 and List[0].Count equals n then the current record is the answer

The total complexity is m * O(n). Also, m must be equal or larger then log(n) to make all members connected. This way the solution complexity is at least O(log(n) * n)

Two problems with this method:

- Getting a group id for a member is too slow (O(n))
- Merging groups is slow (O(n)) in the worst-case scenario

## Straightforward Solution with HashSet:

**Time Complexity** **Analysis**:

HashSet.Add(newFriend) -> O(1) if Count is less than Capacity, otherwise O(k) where k is Count

HashSet.UnionWith(anotherHashSet) -> O(l) if Capacity is less than Count plus l, otherwise O(Count + l) where l is anotherHashSet.Count

HashSet.Contains(member) -> O(1)

Loop:

- Take a record from the log
- Get groups ids for each member {HashSet.Contains(member)} -> 2 * O(1)
- If the ids are the same then do nothing
- If one of the ids is null then add the member {HashSet.Add(newFriend) -> O(1) or O(k)
- If both are null then create new Group {new HashSet{a, b}} -> O(2)
- If not null and different then merge groups {HashSet.UnionWith} -> O(l)
- If the base List.Count is 1 and List[0].Count equals n then the current record is the answer

The total complexity is m * O(l). It is possible to minimize l by comparing HashSet.Count and anotherHashSet.Count, and then adding smallest to the biggest.

This way the total complexity is about O(m * log(n)) which makes the answer acceptable.