The Earliest Moment When Everyone Become Friends

Problem Statement

In this problem, we are given n individuals in a social group, uniquely identified by labels from 0 to n - 1. Alongside, there's an array logs, where each element logs[i] = [timestampi, xi, yi] represents a friendship forming between person xi and person yi at the specific timestampi.

The notion of friendship here is symmetric, meaning if person a is friends with person b, then person b is friends with person a. Moreover, acquaintance extends transitively through friends of friends: if a is friends with someone who is acquainted with b, then a is also acquainted with b.

The task is to determine the earliest timestamp at which every individual in the group is acquainted with every other individual. If such a timestamp does not exist where all persons are interconnected through a chain of acquaintances, the function should return -1.

Examples

Example 1

Input:

logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], n = 6

Output:

20190301

Explanation:

The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5].
The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5].
The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5].
The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4].
The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens.
The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.

Example 2

Input:

logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4

Output:

3

Explanation:

At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

Constraints

• 2 <= n <= 100
• 1 <= logs.length <= 104
• logs[i].length == 3
• 0 <= timestampi <= 109
• 0 <= xi, yi <= n - 1
• xi != yi
• All the values timestampi are unique.
• All the pairs (xi, yi) occur at most one time in the input.

Approach and Intuition

Given the nature of the problem, where we need to track the formation of connections over time until a fully interconnected network is formed, the Union-Find data structure (also known as Disjoint Set Union, DSU) emerges as an optimal solution. This structure not only helps in managing a dynamic network of nodes but also supports quick union operations and efficient checks for connectivity between any two nodes.

1. Initialization:

   • Start by initializing the Union-Find structure for n individuals. Each person starts as their own distinct set, essentially not connected to anyone else.

2. Processing Logs:

   • Process each event in the logs array, which is sorted in ascending order based on timestamps. For each log:
     • Use the Union operation to merge the sets of the two individuals forming a friendship at that timestamp.
     • After each union operation, check if all persons belong to a single set. This can be efficiently tracked by maintaining a count of the number of distinct sets in the Union-Find structure and updating it on each union operation.

3. Earliest Timestamp for Total Acquaintance:

   • The first moment when just one distinct set remains (when the count of distinct sets drops to one) is our required timestamp indicating that all individuals are acquainted. Record and return this timestamp.
   • If, after processing all logs, more than one set remains, return -1, indicating that not all people became interconnected.

Optimizations and Considerations:

• The Union-Find operations can be optimized using path compression and union by rank, which helps in keeping the tree structures flat and speeding up future operations.
• If the total number of people n is equal to 2, the first log event directly answers the problem, as connecting the two individuals means everyone is acquainted.
• It's crucial to ensure that logs are processed in chronological order, as reversing the order could yield incorrect results. Given the constraint that timestamps are unique, sorting them even if they were not provided in order could be a feasible step.

By employing the above approach, one can effectively find the earliest time at which every person became acquainted with every other person or determine if it's not possible.

Solutions

class AcquisitionTracker {
    public int findEarliestMerge(int[][] events, int totalPeople) {
        // Sorting events based on timestamp
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
    
        // Start with each person as a separate community
        int communities = totalPeople;
        DisjointSet ds = new DisjointSet(totalPeople);
    
        for (int[] event : events) {
            int time = event[0], person1 = event[1], person2 = event[2];
    
            // Merge communities and reduce the count if necessary
            if (ds.union(person1, person2)) {
                communities--;
            }
    
            // All persons connected
            if (communities == 1) {
                return time;
            }
        }
    
        // Return -1 if not all persons are connected
        return -1;
    }
}
    
class DisjointSet {
    private int[] parent;
    private int[] size;
    
    public DisjointSet(int capacity) {
        parent = new int[capacity];
        size = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
    
        if (rootX == rootY) return false;
    
        if (size[rootX] > size[rootY]) {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        } else {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    
        return true;
    }
}

class Solution:
    def earliestAcquisition(self, logs: List[List[int]], members: int) -> int:
        logs.sort(key=lambda x: x[0])
    
        group_union = UnionFinder(members)
        remaining_groups = members
    
        for time, person1, person2 in logs:
            if group_union.link(person1, person2):
                remaining_groups -= 1
    
            if remaining_groups == 1:
                return time
    
        return -1
    
    
class UnionFinder:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0] * size
    
    def locate(self, member):
        if self.parent[member] != member:
            self.parent[member] = self.locate(self.parent[member])
        return self.parent[member]
    
    def link(self, member1, member2):
        root1 = self.locate(member1)
        root2 = self.locate(member2)
        connected = False
        if root1 == root2:
            return connected
    
        connected = True
        if self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
        elif self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        else:
            self.parent[root1] = root2
            self.rank[root2] += 1
    
        return connected