Posted on by Dmitrii

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:

using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
var log = new FrienshipRecord[] {
new FrienshipRecord() { Time = 0, Member1 = "a", Member2 = "b" },
new FrienshipRecord() { Time = 1, Member1 = "c", Member2 = "d" },
new FrienshipRecord() { Time = 2, Member1 = "d", Member2 = "e" },
new FrienshipRecord() { Time = 3, Member1 = "f", Member2 = "e" },
new FrienshipRecord() { Time = 4, Member1 = "a", Member2 = "f" },
new FrienshipRecord() { Time = 5, Member1 = "c", Member2 = "a" },
};
var socialNetwork = new List<List<string>>();
int totalMembersCount = 6;
foreach (var record in log)
{
var group1 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member1)); // O(n)
var group2 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member2)); // O(n)
switch (group1 is null, group2 is null)
{
case (false, false) when group1 == group2:
// do nothing
break;
case (false, false) when group1 != group2:
group1.AddRange(group2); // O(l)
socialNetwork.Remove(group2); // O(1)
break;
case (false, true):
group1.Add(record.Member2); // O(1) or O(k)
break;
case (true, false):
group2.Add(record.Member1); // O(1) or O(k)
break;
case (true, true):
socialNetwork.Add(new List<string>() { record.Member1, record.Member2 }); // O(2)
break;
}
// If the social network contains only one group
// and also the grop contains all the members
if (socialNetwork.Count == 1 && socialNetwork[0].Count == totalMembersCount) // O(1)
{
Console.WriteLine("All members were friends at " + record.Time);
return;
}
}
Console.WriteLine("Not all of the members are friends yet");
}
}
internal struct FrienshipRecord
{
internal int Time;
internal string Member1;
internal string Member2;
}
}
view raw List<List<string>> hosted with ❤ by GitHub

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:

using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
var log = new FrienshipRecord[] {
new FrienshipRecord() { Time = 0, Member1 = "a", Member2 = "b" },
new FrienshipRecord() { Time = 1, Member1 = "c", Member2 = "d" },
new FrienshipRecord() { Time = 2, Member1 = "d", Member2 = "e" },
new FrienshipRecord() { Time = 3, Member1 = "f", Member2 = "e" },
new FrienshipRecord() { Time = 4, Member1 = "a", Member2 = "f" },
new FrienshipRecord() { Time = 5, Member1 = "c", Member2 = "a" },
};
var socialNetwork = new List<HashSet<string>>();
int totalMembersCount = 6;
foreach (var record in log)
{
var group1 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member1));
var group2 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member2));
switch (group1 is null, group2 is null)
{
case (false, false) when group1 == group2:
// do nothing
break;
case (false, false) when group1 != group2:
MergeGroups(socialNetwork, group1, group2);
break;
case (false, true):
group1.Add(record.Member2);
break;
case (true, false):
group2.Add(record.Member1);
break;
case (true, true):
socialNetwork.Add(new HashSet<string>() { record.Member1, record.Member2 });
break;
}
// If the social network contains only one group
// and also the grop contains all the members
if (socialNetwork.Count == 1 && socialNetwork[0].Count == totalMembersCount)
{
Console.WriteLine("All members were friends at " + record.Time);
return;
}
}
Console.WriteLine("Not all of the members are friends yet");
}
private static void MergeGroups(
List<HashSet<string>> socialNetwork,
HashSet<string> group1,
HashSet<string> group2)
{
if (group1.Count > group2.Count)
{
group1.UnionWith(group2);
socialNetwork.Remove(group2);
}
else
{
group2.UnionWith(group1);
socialNetwork.Remove(group1);
}
}
}
internal struct FrienshipRecord
{
internal int Time;
internal string Member1;
internal string Member2;
}
}
view raw List<HashSet<string>> hosted with ❤ by GitHub

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.

Leave a Reply

Your email address will not be published. Required fields are marked *