The Earliest Moment When Everyone Become Friends

The Earliest Moment When Everyone Become Friends

What is this problem about?

In The Earliest Moment When Everyone Become Friends coding problem, you are given a list of logs, where each log contains a timestamp and the IDs of two people who became friends. Friendship is mutual and transitive (if A is friends with B and B is friends with C, then A is friends with C). Your task is to find the earliest timestamp at which everyone in the group is connected to each other as friends. If this never happens, return -1.

Why is this asked in interviews?

Google and Expedia ask this "Medium" level question to test a candidate's knowledge of the Union Find data structure. It evaluates whether you can handle chronological events and maintain group connectivity efficiently. It's a classic application of the "Disjoint Set Union" (DSU) pattern, requiring you to track the number of connected components in a graph as edges are added over time.

Algorithmic pattern used

The primary algorithmic pattern is Union Find and Sorting.

1. Sorting: First, sort all friendship logs by their timestamp in ascending order.
2. Union Find (DSU): Initialize a DSU structure for n people. Keep track of the number of connected components (initially n).
3. Iteration: Iterate through the sorted logs. For each log (timestamp, personA, personB):
   • Perform a union operation on personA and personB.
   • If the union actually merged two different groups, decrement the component count.
   • If the component count reaches 1, return the current timestamp.
4. If you finish all logs and count is still > 1, return -1.

Example explanation

Logs: [(2, 0, 1), (5, 2, 3), (1, 1, 2)], n = 4.

1. Sort logs: [(1, 1, 2), (2, 0, 1), (5, 2, 3)].
2. Time 1: Connect 1 and 2. Components: {0}, {1, 2}, {3}. Count = 3.
3. Time 2: Connect 0 and 1. Since 1 is with 2, everyone is now {0, 1, 2}, {3}. Count = 2.
4. Time 5: Connect 2 and 3. Since 2 is with {0, 1}, everyone is now {0, 1, 2, 3}. Count = 1. Result: Timestamp 5.

Common mistakes candidates make

A common mistake is not sorting the logs by timestamp first, which leads to incorrect results if friendship events are processed out of order. Another error is not efficiently implementing the Union Find structure (e.g., failing to use path compression or union by rank/size), which can lead to O(n) operations instead of nearly O(1). Some also forget to initialize the component count correctly.

Interview preparation tip

When preparing for The Earliest Moment When Everyone Become Friends coding problem, master the Union Find interview pattern. It is the go-to solution for any problem involving "connectivity" or "group merging." Being able to explain the "transitive property" of friendship in terms of graph components will impress your interviewer.