Skip to main content
Talentd

The Earliest Moment When Everyone Become Friends - Solution & Explanation

MediumPremiumFree on FleetCodeArrayUnion FindSorting13 min readAsked at: Uber, Expedia, Google
Practice this problem

Problem Statement

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

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 <= 104
  • logs[i].length == 3
  • 0 <= timestampi <= 109
  • 0 <= xi, yi <= n - 1
  • xi != yi
  • All the values timestampi are unique.
  • All the pairs (xi, yi) occur at most one time in the input.

Approach Overview

Problem Overview: You receive friendship logs in the format [timestamp, personA, personB]. Each log means two people became friends at that time. The goal is to return the earliest timestamp when everyone in a group of n people becomes connected through direct or indirect friendships.

Approach 1: Incremental Graph + Connectivity Check (Brute Force) (Time: O(m * n), Space: O(n + m))

Process logs in chronological order and build a graph where nodes represent people and edges represent friendships. After each log, run a traversal such as DFS or BFS to check if all n nodes are connected. This requires iterating through the adjacency list and visiting every node, which costs O(n + m) per check. Repeating this after each friendship event leads to roughly O(m * n) time in dense scenarios. This approach works for small inputs but becomes slow when the number of logs grows.

Approach 2: Sorting + Union-Find (Optimal) (Time: O(m log m), Space: O(n))

Sort the logs by timestamp, then process them in chronological order. Use a Disjoint Set Union (DSU) structure to track connected components. Each friendship event performs a union(a, b), merging two groups if they were previously separate. Maintain a counter of remaining components; once it becomes 1, everyone is connected. Union-Find with path compression and union by rank keeps operations nearly constant time. The dominant cost becomes sorting the logs (O(m log m)), making this approach scalable for large inputs.

The key insight: the earliest moment when everyone becomes friends is exactly when the number of connected components drops to one. Union-Find tracks this efficiently without repeatedly traversing the graph.

Relevant concepts include Union-Find, Sorting, and Array processing for handling the input logs.

Recommended for interviews: Sorting + Union-Find is the expected solution. Interviewers want to see that you recognize this as a dynamic connectivity problem. Showing the brute-force graph traversal demonstrates baseline reasoning, but implementing Union-Find proves you understand scalable connectivity algorithms.

Approach 1: Sorting + Union-Find

We sort all the logs in ascending order by timestamp, then traverse the sorted logs. Using a union-find set, we check whether the two people in the current log are already friends. If they are not friends, we merge them into one friend circle, until everyone is in one friend circle, then return the timestamp of the current log.

If we have traversed all the logs and not everyone is in one friend circle, then return -1.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of logs.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting + Union-Find—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Incremental Graph + DFS/BFS Connectivity CheckO(m * n)O(n + m)Useful for understanding the problem or when constraints are small
Sorting + Union-FindO(m log m)O(n)Best general solution for large inputs and typical interview expectations

Video Solution

THE EARLIEST MOMENT WHEN EVERYONE BECOMES FRIENDS | LEETCODE 1101 | PYTHON GRAPH SOLUTION • Cracking FAANG • 5,439 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice The Earliest Moment When Everyone Become Friends with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Provinces