1101. The Earliest Moment When Everyone Become Friends

The Earliest Moment When Everyone Become Friends (LeetCode 1101) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.

How to solve The Earliest Moment When Everyone Become Friends

The Earliest Moment When Everyone Become Friends is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.

Work towards the solution in these steps:

1. Sort the log items by their timestamp.
2. How can we model this problem as a graph problem?
3. Let's use a union-find data structure. At the beginning we have a graph with N nodes but no edges.

The reference solution runs in O(nlogn) time and O(n) space.

The The Earliest Moment When Everyone Become Friends solution and editorial walks through the full approach with reference code.

Problem statement

You are given an integer n representing the number of people in a social group, labeled from 0 to n - 1. You are also given a list of logs logs, where each logs[i] = [timestamp, x, y] indicates that person x and person y became friends at time timestamp.

Friendship is transitive: if person a is a friend of person b, and person b is a friend of person c, then person a is also a friend of person c. A group of people are considered to be all friends if every pair of people are directly or indirectly friends.

Return the earliest timestamp at which everyone in the group became friends. If there is no such moment, return -1.

Constraints: - n == number of people in the group, 1 <= n <= 100 - 1 <= logs.length <= 10^4 - logs[i].length == 3 - 0 <= timestamp <= 10^9 - 0 <= x, y <= n - 1 - x != y - All timestamp values in logs are not necessarily in order

Note: If multiple events happen at the same timestamp, they can occur in any order.

Examples

Topics and companies

Topics: Array, Union Find, Sorting.

Reported in interviews at Google.

How to practise The Earliest Moment When Everyone Become Friends on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open The Earliest Moment When Everyone Become Friends in the code editor, or read the The Earliest Moment When Everyone Become Friends editorial for a worked solution with its approach and complexity analysis.

Where The Earliest Moment When Everyone Become Friends sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Union-Find (Disjoint Set Union - DSU) subpattern
• The full DSA patterns sheet

Problems related to The Earliest Moment When Everyone Become Friends

Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:

• Accounts Merge — Medium, same subpattern
• Graph Valid Tree — Medium, same subpattern
• Greatest Common Divisor Traversal — Hard, same subpattern
• Largest Component Size by Common Factor — Hard, same subpattern
• Most Stones Removed with Same Row or Column — Medium, same subpattern
• Number of Connected Components in an Undirected Graph — Medium, same subpattern

The Earliest Moment When Everyone Become Friends FAQ