Problem Description

You have n people in a social group, labeled from 0 to n - 1. You're given an array logs where each entry logs[i] = [timestamp_i, x_i, y_i] indicates that person x_i and person y_i become friends at time timestamp_i.

The friendship relationship has two important properties:

• Symmetric: If person a is friends with person b, then person b is also friends with person a
• Transitive through acquaintance: Person a is considered acquainted with person b if:
  • a is directly friends with b, OR
  • a is friends with someone who is acquainted with b (friendship chains)

Your task is to find the earliest timestamp when every person becomes acquainted with every other person in the group. In other words, find the minimum time when all n people form a single connected network through their friendship relationships.

If it's impossible for everyone to become acquainted (meaning the friendships never connect all people into one group), return -1.

For example, if we have 4 people and the following logs:

• At time 1: person 0 and 1 become friends
• At time 2: person 1 and 2 become friends
• At time 3: person 2 and 3 become friends

Then at time 3, everyone is acquainted with everyone else through the chain of friendships, so the answer would be 3.

Intuition

The key insight is that we need to find when all people form a single connected component. This is a classic Union-Find (Disjoint Set Union) problem.

Think of the friendship network as a graph where each person is a node and each friendship is an edge. Initially, we have n isolated nodes (each person is their own component). As friendships form over time, these separate components start merging together. We want to find the exact moment when all these components merge into one.

Since we want the earliest time this happens, we should process the friendships in chronological order. By sorting the logs by timestamp, we can simulate the friendship formation process as it happens over time.

The Union-Find data structure is perfect for this because it efficiently:

1. Tracks which connected component each person belongs to (using the find operation)
2. Merges two components when a new friendship forms (using the union operation)
3. Allows us to count how many separate components remain

Starting with n separate components, each time we successfully merge two different components (when two people from different groups become friends), we decrease our component count by 1. When we reach exactly 1 component, everyone is connected - that's our answer!

The beauty of this approach is that we don't need to check all pairs of people to see if they're connected. We just need to track when the number of separate friend groups reduces to 1. If we process all friendships and still have more than 1 component, it means not everyone can be acquainted, so we return -1.

Learn more about Union Find and Sorting patterns.

Solution Approach

The solution implements the Union-Find algorithm with path compression to efficiently track and merge friend groups.

Step 1: Initialize the Union-Find Structure

p = list(range(n))

We create a parent array p where initially each person is their own parent (representing n separate components). p[i] = i means person i is the root of their own component.

Step 2: Sort the Logs by Timestamp

for t, x, y in sorted(logs):

We sort the logs in ascending order by timestamp to process friendships chronologically. This ensures we find the earliest possible time when everyone becomes connected.

Step 3: Find Operation with Path Compression

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

The find function returns the root representative of a person's component. Path compression (p[x] = find(p[x])) optimizes future lookups by directly pointing each node to the root.

Step 4: Process Each Friendship For each log entry [t, x, y]:

• First check if x and y are already in the same component using find(x) == find(y)
• If they're already connected, skip this friendship (continue to next)
• If they're in different components:
  • Merge the components: p[find(x)] = find(y) (make one root point to the other)
  • Decrease the component count: n -= 1
  • Check if we've reached a single component: if n == 1: return t

Step 5: Handle Disconnected Case If we process all logs and n > 1 (multiple components remain), return -1 as not everyone can be acquainted.

The algorithm's efficiency comes from:

• Sorting: O(m log m) where m is the number of logs
• Union-Find operations: Nearly O(1) amortized time per operation with path compression
• Overall complexity: O(m log m) dominated by the sorting step

Example Walkthrough

Let's walk through a concrete example with 6 people (labeled 0-5) and the following friendship logs:

logs = [[3, 0, 1], [7, 0, 2], [4, 3, 4], [6, 3, 5], [9, 2, 5]]

Initial State (before any friendships):

• Parent array: p = [0, 1, 2, 3, 4, 5]
• Each person is their own parent (6 separate components)
• Component count: n = 6

Step 1: Sort logs by timestamp After sorting: [[3, 0, 1], [4, 3, 4], [6, 3, 5], [7, 0, 2], [9, 2, 5]]

Step 2: Process timestamp 3 - [3, 0, 1]

• Find(0) = 0, Find(1) = 1 (different components)
• Union: Set p[0] = 1 (0's parent becomes 1)
• Components: {0,1}, {2}, {3}, {4}, {5}
• Count: n = 5

Step 3: Process timestamp 4 - [4, 3, 4]

• Find(3) = 3, Find(4) = 4 (different components)
• Union: Set p[3] = 4 (3's parent becomes 4)
• Components: {0,1}, {2}, {3,4}, {5}
• Count: n = 4

Step 4: Process timestamp 6 - [6, 3, 5]

• Find(3) = 4 (trace: 3→4), Find(5) = 5 (different components)
• Union: Set p[4] = 5 (4's parent becomes 5)
• Components: {0,1}, {2}, {3,4,5}
• Count: n = 3

Step 5: Process timestamp 7 - [7, 0, 2]

• Find(0) = 1 (trace: 0→1), Find(2) = 2 (different components)
• Union: Set p[1] = 2 (1's parent becomes 2)
• Components: {0,1,2}, {3,4,5}
• Count: n = 2

Step 6: Process timestamp 9 - [9, 2, 5]

• Find(2) = 2, Find(5) = 5 (different components)
• Union: Set p[2] = 5 (2's parent becomes 5)
• Components: {0,1,2,3,4,5} (all connected!)
• Count: n = 1
• Return 9 (earliest time when everyone is acquainted)

The key insight: We tracked when separate friend groups merged. At timestamp 9, the two remaining groups {0,1,2} and {3,4,5} finally connected through the friendship between persons 2 and 5, creating one unified network where everyone is acquainted with everyone else.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × log m + m × α(n)), where m is the number of logs and n is the number of people. The O(m × log m) comes from sorting the logs array, and O(m × α(n)) comes from performing at most m union-find operations, where α(n) is the inverse Ackermann function (practically constant). Since α(n) is effectively constant for all practical values, this simplifies to O(m × log m).

The space complexity is O(n) for storing the parent array p of size n, which represents the disjoint set union (DSU) data structure. The sorting operation uses O(log m) space for the recursion stack in typical implementations, but since n ≤ m in most cases, the dominant space usage is O(n).

Note: The reference answer uses n to denote the number of logs, which creates confusion with the parameter n in the code that represents the number of people. In the code, n is the number of people, and the logs array has length m. The reference answer's notation would make the time complexity O(n × log n) and space complexity O(n) where this n refers to the length of the logs array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Sort the Logs

One of the most common mistakes is processing the logs in the given order instead of sorting them by timestamp first. This would lead to incorrect results since we need to find the earliest time when everyone becomes connected.

Wrong approach:

# Processing logs without sorting
for timestamp, person_x, person_y in logs:  # Wrong!
    # Union-find operations...

Correct approach:

# Sort logs by timestamp first
for timestamp, person_x, person_y in sorted(logs):
    # Union-find operations...

2. Incorrect Union Operation

Another frequent error is performing the union operation on the persons directly instead of their root parents. This breaks the Union-Find structure and leads to incorrect component tracking.

Wrong approach:

# Directly connecting persons instead of roots
if find(person_x) != find(person_y):
    parent[person_x] = person_y  # Wrong!
    num_groups -= 1

Correct approach:

# Connect the root parents
root_x = find(person_x)
root_y = find(person_y)
if root_x != root_y:
    parent[root_x] = root_y  # Correct!
    num_groups -= 1

3. Not Implementing Path Compression

While the solution would still be correct without path compression, omitting it can lead to performance issues with large inputs. The find operation could degrade to O(n) in the worst case, making the overall complexity O(m*n) instead of the optimal O(m log m).

Inefficient approach:

def find(person):
    while parent[person] != person:
        person = parent[person]
    return person

Optimized approach with path compression:

def find(person):
    if parent[person] != person:
        parent[person] = find(parent[person])  # Path compression
    return parent[person]

4. Off-by-One Error in Component Counting

Some implementations might incorrectly initialize or update the component count, leading to premature or delayed return of the result.

Common mistakes:

• Starting with num_groups = 0 instead of num_groups = n
• Checking if num_groups == 0 instead of if num_groups == 1
• Decrementing the counter even when the persons are already connected

Correct implementation:

num_groups = n  # Start with n separate groups
for timestamp, person_x, person_y in sorted(logs):
    root_x = find(person_x)
    root_y = find(person_y)
    if root_x != root_y:  # Only decrement when actually merging
        parent[root_x] = root_y
        num_groups -= 1
        if num_groups == 1:  # Check for exactly 1 group
            return timestamp