⚡Flashcard Drill➔
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

  1. Process the meetings grouped by time, in increasing time order.
  2. Within one time slice, build a subgraph and BFS from everyone who already knows the secret.
  3. Everyone reachable in that subgraph learns the secret, and only then is the next time slice processed.
  4. 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 firstPerson at time 0: both start in known.
⚡
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 Graphs Problems