Is The Earliest Moment When Everyone Become Friends easy or hard?

The problem is typically classified as Medium difficulty. The challenge comes from recognizing it as a dynamic connectivity problem and applying Union-Find correctly rather than using repeated graph traversals.

The Earliest Moment When Everyone Become Friends Python/Java solution

Most implementations follow the same pattern: sort logs by timestamp, initialize a Union-Find structure for n people, and process each log with a union operation. When the number of components reaches one, return that timestamp. The approach works the same in Python, Java, C++, Go, and other languages.

How to solve The Earliest Moment When Everyone Become Friends in O(n)?

A true O(n) solution is not possible because the logs must be processed in chronological order, which requires sorting when the input is unsorted. The best achievable complexity is O(m log m) using sorting plus Union-Find. After sorting, each union operation runs in near constant time.

What is the best approach for The Earliest Moment When Everyone Become Friends?

The optimal approach is Sorting + Union-Find. First sort all friendship logs by timestamp, then union the two people in each log using a Disjoint Set Union structure. Track the number of connected components and return the timestamp when it becomes one. The time complexity is O(m log m) due to sorting.

Is The Earliest Moment When Everyone Become Friends asked at Google/Amazon/Meta?

This problem tests dynamic connectivity using Union-Find, a common interview topic at companies like Google, Amazon, and Meta. Variants involving connectivity over time or merging groups appear frequently in system and algorithm interviews.

What data structure is used in The Earliest Moment When Everyone Become Friends?

The key data structure is Union-Find (Disjoint Set Union). It efficiently tracks connected components and supports union and find operations with path compression and union by rank, allowing near constant-time connectivity updates.

What is the time complexity of The Earliest Moment When Everyone Become Friends?

The optimal solution runs in O(m log m) time where m is the number of logs. Sorting the logs dominates the runtime, while each Union-Find operation is nearly constant time with path compression and union by rank. Space complexity is O(n) for storing parent and rank arrays.

Description Hints 4 Solution Video 12:02

1101. The Earliest Moment When Everyone Become Friends

Medium66.0% acceptance3 companiesPremium elsewhere, free here

There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestamp_i, x_i, y_i] indicates that x_i and y_i will be friends at the time timestamp_i.

Friendship is symmetric. That means if a is friends with b, then b is friends with a. Also, person a is acquainted with a person b if a is friends with b, or a is a friend of someone acquainted with b.

Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return -1.

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 <= 10⁴
logs[i].length == 3
0 <= timestamp_i <= 10⁹
0 <= x_i, y_i <= n - 1
x_i != y_i
All the values timestamp_i are unique.
All the pairs (x_i, y_i) occur at most one time in the input.

Asked at 3 companies

Uber Expedia

Google

Topics

Hints open one at a time

Hint 1

Sort the log items by their timestamp.

Hint 2

How can we model this problem as a graph problem?

Hint 3

Let's use a union-find data structure. At the beginning we have a graph with N nodes but no edges.

Hint 4

Then we loop through the events and unite each node until the number of connected components reach to 1. Notice that each time two different connected components are united the number of connected components decreases by 1.

12:02

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution