MediumArrayUnion FindSortingUpdated Sep 2026

1101. The Earliest Moment When Everyone Become Friends

Asked at Uber

Difficulty

Medium

Time

O(m log m)

Space

O(n)

Pattern

Array

Companies

1

Problem

There are n people, labeled 0 to n - 1. You are given a list logs, where each entry [timestamp, x, y] means person x and person y become friends at that moment.

Friendship spreads: if a is friends with b, and b is friends with c, then a and c are also connected (friends of friends count). Two people are acquainted when there is a chain of friendships linking them.

Return the earliest timestamp at which every person is acquainted with every other person. That means all n people form one single group. If that never happens, return -1.

Groups merge over time

logs[20190101,0,1][20190104,3,4][20190107,2,3][20190211,1,5][20190301,0,3]01234The event at 20190301 merges the last two groups into one
Each event joins two people; we want the first moment all n people sit in one group.

Constraints

  • ●2 <= n <= 100
  • ●1 <= logs.length <= 10^4
  • ●logs[i].length == 3
  • ●0 <= timestamp_i <= 10^9
  • ●0 <= x_i, y_i <= n - 1
  • ●x_i != y_i
  • ●All timestamp values are unique.
  • ●Each pair (x, y) appears at most once.

Examples

Example 1
Inputlogs = [[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
Output20190301
WhyGroups grow like this: [0,1],[2],[3],[4],[5] → [0,1],[2],[3,4],[5] → [0,1],[2,3,4],[5] → [0,1,5],[2,3,4]. The event at 20190224 joins 2 and 4, but they are already in the same group, so nothing changes. At 20190301 the pair 0 and 3 links the two remaining groups, giving one group of all 6 people.
Example 2
Inputlogs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output3
WhyAt time 0, {0,2} join. At time 1, 0 and 1 join, so {0,1,2}. At time 3, 0 and 3 join, so all four people {0,1,2,3} are in one group. That is the first moment everyone is connected.

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

Sort the log entries by timestamp in ascending order.

2

Process each friendship event in chronological order and maintain connected components using Union-Find.

3

After each union operation, check if all n people belong to the same connected component.

4

The number of components can be tracked: start with n components and decrement on each successful union.

5

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.

Union-Find with a component counter

parent012345012345Start: every person is their own group, components = 6parent002345012345After [20190101,0,1]: 1 points to 0, components = 5parent002230012345After [20190301,0,3]: the two groups merge, components= 1sort logs by timestampunion(a,b) → components -= 1components == 1 → return timestamp
Start with n groups. Every successful merge drops the count by one; when it hits 1 we are done.
ComplexityTime O(m log m)Space O(n)m is the number of logs; sorting them dominates, while each union/find is nearly constant time.

What Trips People Up in Real Interviews

1

Clarify whether timestamps are guaranteed to be unique; if not, decide how to handle ties.

2

Confirm that the answer is the timestamp of the event that makes everyone connected, not the next timestamp.

3

If after processing all events no one is fully connected, return -1.

4

Union-Find is preferred over BFS/DFS for this problem because edges arrive over time.

5

Edge case: if n is 0 or 1, everyone is already friends, so return 0.

Solution Code

O(m log m) time
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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(m log m) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.