Domain 2MediumMEDIUM

The Earliest Moment When Everyone Become Friends

Sorts friendship events chronologically and uses a Disjoint Set Union (DSU) structure to track connected components until only one remains, returning the timestamp when full connectivity is achieved or -1 if impossible.

Domain: medium•Updated: 2026-09-08
#Union-Find#Array/DSU#O(L log L)#O(N)

Problem Breakdown

We are given N people with IDs from 0 to N-1. A list of logs describes friendship events at specific timestamps, where each log connects two individuals. The goal is to find the earliest timestamp by which all N individuals belong to a single connected component (everyone knows everyone).

Inputs:

  • logs: List of [timestamp, id_A, id_B]. Crucially unsorted.
  • N: Integer representing total people count.

Outputs:

  • The earliest timestamp achieving full connectivity.
  • -1 if the graph remains disconnected after processing all logs.

Constraints & Edge Cases:

  • Unsorted Input: Processing must occur in chronological order, requiring sorting of logs.
  • Disconnected Graphs: If components > 1 remain after iterating through all events, return -1.
  • Redundant Connections: Connecting already connected individuals does not reduce component count; logic continues to check for new connections.
  • N Range: Small (2 <= N <= 100). This allows efficient DSU operations without strict optimization needs beyond path compression.

Intuition

The problem asks for the earliest time point when a graph becomes fully connected (single component) as edges are added over time. Since we need to track connectivity dynamically, Disjoint Set Union (DSU) is ideal because it efficiently manages merging sets and checking if two elements belong to the same set in nearly constant amortized time.

Why not Brute Force? Checking full graph connectivity via BFS/DFS after every edge addition would be O(N + E) per step, leading to higher overall complexity compared to DSU’s near-constant updates. Since logs are unsorted, we must sort them first (O(L log L)) before simulating the timeline.

Key Insight: We only care about when num_components drops from N down to 1. We can track this count directly in our DSU state and return immediately upon reaching 1 component. This ensures O(1) retrieval of the answer once connectivity is achieved, avoiding unnecessary checks after that point.

Approach

  1. Sort Logs: Sort the input list by timestamp ascending so we simulate events chronologically from earliest to latest.
  2. Initialize DSU: Create a parent array where parent[i] = i. Initialize num_components (count of disjoint sets) to N.
  3. Iterate and Union: Loop through each sorted log:
    • Find the root parents for both people in the current log (find(id_A) and find(id_B)).
    • If roots are different, union them by setting one parent to point to another (using path compression) and decrement num_components.
  4. Check Condition: After each successful union that reduces components:
    • Check if num_components == 1. If true, return the current log’s timestamp immediately as it is the earliest moment full connectivity was achieved.
  5. Final Fallback: If the loop finishes and we haven’t returned a timestamp (meaning graph never fully connected), return -1.

Complexity Analysis

  • Time Complexity: O(L * α(N) + L log L). Sorting takes O(L log L). The DSU operations take nearly constant time per operation, specifically proportional to the Inverse Ackermann function α(N) which is effectively ≤ 4 for practical inputs. Thus, sorting dominates or balances with processing depending on constraints (L up to 10^4 vs N=100).
  • Space Complexity: O(N) for storing parent pointers and rank/size arrays in the DSU structure. Sorting may take additional space proportional to L if not done in-place, but typically considered auxiliary space is dominated by input storage or negligible here.

Solution

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        
    def find(self, x):
        # Path compression for efficiency
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        # Only merge if they are in different sets
        if rootX != rootY:
            self.parent[rootX] = rootY
            return True  # Indicates a successful union (new connection formed between components)
        return False

def getEarliestMoment(logs, N):
    # Sort logs by timestamp to process events chronologically
    logs.sort(key=lambda x: x[0])
    
    uf = UnionFind(N)
    num_components = N
    
    for log in logs:
        _, u, v = log
        
        if uf.union(u, v):
            num_components -= 1
            
        # If everyone is connected (only one component left), return timestamp immediately
        if num_components == 1:
            return log[0]
            
    # If loop completes and components > 1, graph never fully connected
    return -1

# Example usage matching problem description logic
if __name__ == "__main__":
    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
    print(getEarliestMoment(logs, N)) # Output: 20190301

Edge Cases Handled

  • Unsorted Logs: The solution explicitly sorts logs by timestamp at the start to ensure chronological processing.
  • Disconnected Graph: If after iterating all logs num_components > 1, the function returns -1.
  • Redundant Edges: When two people are already connected, union() returns False and component count doesn’t change; logic continues correctly without returning early incorrectly.
  • N=2 Minimum Case: Logic holds for minimum N where a single successful union reduces components from 2 to 1 immediately.