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
- This is a connectivity problem: sort the logs by timestamp and union the pairs one by one.
- Use union-find and track the number of connected components. Each successful union decrements the count.
- The answer is the timestamp at which the component count first reaches 1.
- If
n == 1the 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 == 1case: the loop would never setgroupsto 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.