The Earliest Moment When Everyone Become Friends
Asked at Uber
Problem
Given a list of timestamps and friend pairs, find the earliest timestamp at which all people in the group have become friends directly or indirectly. Each entry [timestamp, a, b] means person a and person b became friends at the given timestamp.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | MEDIUM | View all Uber questions → |
How to Think About It
Sort the log entries by timestamp in ascending order.
Process each friendship event in chronological order and maintain connected components using Union-Find.
After each union operation, check if all n people belong to the same connected component.
The number of components can be tracked: start with n components and decrement on each successful union.
When the component count reaches 1, return the current timestamp as the answer.
Optimal Approach
Sort the logs by timestamp. Initialize a Union-Find with n people and a component count of n. Process each log in order: if the two people are not already in the same component, union them and decrement the component count. When the component count reaches 1, all people are connected and the current timestamp is the answer. Return -1 if the loop finishes without full connectivity.
What Trips People Up in Real Interviews
Clarify whether timestamps are guaranteed to be unique; if not, decide how to handle ties.
Confirm that the answer is the timestamp of the event that makes everyone connected, not the next timestamp.
If after processing all events no one is fully connected, return -1.
Union-Find is preferred over BFS/DFS for this problem because edges arrive over time.
Edge case: if n is 0 or 1, everyone is already friends, so return 0.
Solution Code
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
class Solution:
def earliestAcq(self, logs, n):
logs.sort(key=lambda x: x[0])
uf = UnionFind(n)
components = n
for timestamp, a, b in logs:
if uf.union(a, b):
components -= 1
if components == 1:
return timestamp
return -1
Frequently Asked Questions
What is the The Earliest Moment When Everyone Become Friends problem?
Given a list of timestamps and friend pairs, find the earliest timestamp at which all people in the group have become friends directly or indirectly. Each entry [timestamp, a, b] means person a and person b became friends at the given timestamp.
How do you solve The Earliest Moment When Everyone Become Friends?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask The Earliest Moment When Everyone Become Friends?
The Earliest Moment When Everyone Become Friends is asked at Uber. It is a medium difficulty problem.
What are common mistakes on The Earliest Moment When Everyone Become Friends?
- Clarify whether timestamps are guaranteed to be unique; if not, decide how to handle ties.
- Confirm that the answer is the timestamp of the event that makes everyone connected, not the next timestamp.
- If after processing all events no one is fully connected, return -1.
- Union-Find is preferred over BFS/DFS for this problem because edges arrive over time.
- Edge case: if n is 0 or 1, everyone is already friends, so return 0.