NeetCode #622LC-2092HardGraphs
← Back to All Problems#622 · #2092 · Find All People With Secret(找出知晓秘密的所有专家)
📌 Problem Statement & Constraints
You are given
n people, meetings where meetings[i] = [x, y, time] means persons x and y meet at that time, and firstPerson. Person 0 knows the secret from the start and shares it with firstPerson at time 0. A person who knows the secret shares it at every meeting they attend. Return all people who know the secret. Constraints: 2 <= n <= 10^5, 1 <= meetings.length <= 10^5, times are distinct per pair.💡 Core Algorithmic Approaches
- Process the meetings grouped by time, in increasing time order.
- Within one time slice, build a subgraph and BFS from everyone who already knows the secret.
- Everyone reachable in that subgraph learns the secret, and only then is the next time slice processed.
- The time grouping is essential: knowledge cannot propagate backwards through time.
💻 Benchmark Python3 Implementation
class Solution:
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
from collections import defaultdict, deque
known = {0, firstPerson}
by_time = defaultdict(list)
for x, y, t in meetings:
by_time[t].append((x, y))
for t in sorted(by_time):
# build the subgraph for this time slice
sub = defaultdict(list)
for x, y in by_time[t]:
sub[x].append(y)
sub[y].append(x)
# BFS from everyone who already knows, within this slice only
q = deque()
seen = set()
for x, y in by_time[t]:
for p in (x, y):
if p in known and p not in seen:
seen.add(p)
q.append(p)
while q:
node = q.popleft()
for nxt in sub[node]:
if nxt not in seen:
seen.add(nxt)
q.append(nxt)
known |= seen # propagate before moving to the next time
return sorted(known)⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + m) log m): the time sort plus a BFS per slice over its edges.
💾 Space Complexity
O(n + m) for the subgraph and the sets.
⚠️ Interview Pitfalls & Follow-ups
- Building one global graph and running a single BFS: knowledge would leak backwards in time.
- Merging all meetings into one component: the same problem.
- Processing times in arbitrary order: the slices must be processed in increasing time.
- Forgetting that person 0 shares with
firstPersonat time 0: both start inknown.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.