⚡Flashcard Drill➔
NeetCode #162LC-1101MediumArrays & Hashing
← Back to All Problems

#162 · #1101 · The Earliest Moment When Everyone Become Friends(彼此熟识的最早时间)

📌 Problem Statement & Constraints

There are n people in a social network. Given logs where logs[i] = [timestamp, idA, idB] means the two people became friends at that time, return the earliest time at which all people are connected (or -1 if it never happens). Constraints: 1 <= n <= 1000, 1 <= logs.length <= 10^4; logs is not necessarily sorted.

💡 Core Algorithmic Approaches

  1. This is a connectivity problem: sort the logs by timestamp and union the pairs one by one.
  2. Use union-find and track the number of connected components. Each successful union decrements the count.
  3. The answer is the timestamp at which the component count first reaches 1.
  4. If n == 1 the answer is 0, since a single person is trivially all-connected.

💻 Benchmark Python3 Implementation

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        if n == 1:
            return 0
        logs.sort(key=lambda x: x[0])      # chronological order
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path halving
                x = parent[x]
            return x

        groups = n
        for t, a, b in logs:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                groups -= 1
                if groups == 1:
                    return t
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m log m + m * alpha(n)) where m is the number of logs: sorting dominates, and the union-find operations are effectively constant.
💾 Space Complexity
O(n) for the parent array.

⚠️ Interview Pitfalls & Follow-ups

  • Processing the logs in input order: they are not sorted by timestamp, so the answer would be wrong.
  • Counting edges instead of components: the answer requires connectivity, not a spanning tree size.
  • Forgetting the n == 1 case: the loop would never set groups to 1 (it starts at 1), so it would fall through to -1. Handle it explicitly.
  • Recomputing connectivity from scratch after each log: O(m * n) instead of the near-linear union-find.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems