The Earliest Moment When Everyone Become Friends

The Earliest Moment When Everyone Become Friends 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.

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.

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

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:

Preparing this workspace.