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.

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