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.
-1if 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
- Sort Logs: Sort the input list by timestamp ascending so we simulate events chronologically from earliest to latest.
- Initialize DSU: Create a parent array where
parent[i] = i. Initializenum_components(count of disjoint sets) toN. - Iterate and Union: Loop through each sorted log:
- Find the root parents for both people in the current log (
find(id_A)andfind(id_B)). - If roots are different, union them by setting one parent to point to another (using path compression) and decrement
num_components.
- Find the root parents for both people in the current log (
- 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.
- Check if
- 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
logsby 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.