Month: August 2020

Posted on

LeetCode: The Earliest Moment When Everyone Become Friends (Solution with Time Complexity Analysis)

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:

  1. Take a record from the log
  2. Get groups ids for each member {List.Contains(member)} -> 2 * O(n)
  3. If the ids are the same then do nothing
  4. If one of the ids is null then add the member {List.Add(newFriend) -> O(1) or O(k)
  5. If both are null then create new Group {new List{a, b}} -> O(2)
  6. If not null and different then merge groups {List.AddRange} -> O(l)
  7. 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:

  1. Getting a group id for a member is too slow (O(n))
  2. 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:

  1. Take a record from the log
  2. Get groups ids for each member {HashSet.Contains(member)} -> 2 * O(1)
  3. If the ids are the same then do nothing
  4. If one of the ids is null then add the member {HashSet.Add(newFriend) -> O(1) or O(k)
  5. If both are null then create new Group {new HashSet{a, b}} -> O(2)
  6. If not null and different then merge groups {HashSet.UnionWith} -> O(l)
  7. 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.