2092. Find All People With Secret - Explanation

1. Depth First Search

Intuition

The secret spreads through meetings in chronological order. At each point in time, all meetings happening simultaneously form a graph where people can share secrets with each other. If anyone in a connected group already knows the secret, everyone in that group learns it by the end of that time slot. We process meetings time by time, using DFS to propagate the secret through connected components.

Algorithm

Initialize a set secrets containing person 0 and firstPerson.
Group all meetings by their time into an adjacency list for each time slot.
Process times in sorted order:
- For each time, build a graph of people meeting at that time.
- For each person who already knows the secret, run DFS to spread it to all connected people.
Return the list of all people who know the secret.

class Solution:
    def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]:
        secrets = set([0, firstPerson])  # People with secret
        time_map = {}  # time -> adjacency list meetings

        for src, dst, t in meetings:
            if t not in time_map:
                time_map[t] = defaultdict(list)
            time_map[t][src].append(dst)
            time_map[t][dst].append(src)

        def dfs(src, adj):
            if src in visit:
                return
            visit.add(src)
            secrets.add(src)
            for nei in adj[src]:
                dfs(nei, adj)

        for t in sorted(time_map.keys()):
            visit = set()
            for src in time_map[t]:
                if src in secrets:
                    dfs(src, time_map[t])

        return list(secrets)

Time & Space Complexity

Time complexity: $O(m \log m + n)$
Space complexity: $O(m + n)$

Where $m$ is the number of meetings and $n$ is the number of people.

2. Breadth First Search

Intuition

This is the same concept as the DFS approach, but we use BFS instead to propagate the secret. At each time slot, we start BFS from all people who already know the secret and explore their meeting connections level by level. Both approaches achieve the same result with similar complexity.

Algorithm

Initialize a set secrets containing person 0 and firstPerson.
Group meetings by time into adjacency lists.
Process times in sorted order:
- Initialize a queue with all secret-holders who have meetings at this time.
- Perform BFS: for each person dequeued, add all their meeting partners to the queue and mark them as knowing the secret.
Return the list of all people who know the secret.

class Solution:
    def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]:
        secrets = set([0, firstPerson])  # People with secret
        time_map = {}  # time -> adjacency list meetings

        for src, dst, t in meetings:
            if t not in time_map:
                time_map[t] = defaultdict(list)
            time_map[t][src].append(dst)
            time_map[t][dst].append(src)

        for t in sorted(time_map.keys()):
            visit = set()
            q = deque()

            for src in time_map[t]:
                if src in secrets:
                    q.append(src)
                    visit.add(src)

            while q:
                node = q.popleft()
                secrets.add(node)
                for nei in time_map[t][node]:
                    if nei not in visit:
                        visit.add(nei)
                        q.append(nei)

        return list(secrets)

Time & Space Complexity

Time complexity: $O(m \log m + n)$
Space complexity: $O(m + n)$

Where $m$ is the number of meetings and $n$ is the number of people.

3. Iterative DFS

Intuition

Instead of using recursion for DFS, we can use an explicit stack. This approach sorts all meetings by time first, then processes groups of meetings with the same timestamp together. For each group, we build an adjacency list and use a stack-based DFS starting from all current secret-holders.

Algorithm

Sort meetings by time.
Initialize a boolean array secrets where only positions 0 and firstPerson are true.
Process meetings in groups by time:
- Build an adjacency list for meetings at the current time.
- Collect all people in this time group who already know the secret.
- Use iterative DFS (stack) to spread the secret to all reachable people.
Return all indices where secrets[i] is true.

class Solution:
    def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]:
        meetings.sort(key=lambda x: x[2])  # Sort by time
        secrets = [False] * n
        secrets[0] = secrets[firstPerson] = True

        for _, group in groupby(meetings, key=lambda x: x[2]):
            adj = defaultdict(list)
            visited = set()

            for u, v, _ in group:
                adj[u].append(v)
                adj[v].append(u)
                if secrets[u]:
                    visited.add(u)
                if secrets[v]:
                    visited.add(v)

            stack = list(visited)
            while stack:
                node = stack.pop()
                for nei in adj[node]:
                    if nei not in visited:
                        visited.add(nei)
                        stack.append(nei)
                        secrets[nei] = True

        return [i for i in range(n) if secrets[i]]

Time & Space Complexity

Time complexity: $O(m \log m + n)$
Space complexity: $O(m + n)$

Where $m$ is the number of meetings and $n$ is the number of people.

4. Disjoint Set Union

Intuition

We can model the secret-sharing as a union-find problem. People who meet at the same time are temporarily connected. If any person in a connected component knows the secret (i.e., is connected to person 0), everyone in that component learns it. The key insight is that after processing each time slot, we must reset people who did not get connected to person 0, since the secret only spreads within a time slot.

Algorithm

Sort meetings by time.
Initialize a DSU structure. Union person 0 and firstPerson.
Process meetings in groups by time:
- Union all pairs of people meeting at this time.
- Track all people involved in meetings at this time.
- After all unions for this time, reset any person not connected to person 0 (they do not know the secret yet).
Return all people who are in the same component as person 0.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

    def reset(self, node):
        self.Parent[node] = node
        self.Size[node] = 1

class Solution:
    def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]:
        meetings.sort(key=lambda x: x[2])  # Sort by time
        dsu = DSU(n)
        dsu.union(0, firstPerson)

        for _, group in groupby(meetings, key=lambda x: x[2]):
            group_nodes = set()
            for u, v, _ in group:
                dsu.union(u, v)
                group_nodes.add(u)
                group_nodes.add(v)

            for node in group_nodes:
                if dsu.find(node) != dsu.find(0):
                    dsu.reset(node)

        return [i for i in range(n) if dsu.find(i) == dsu.find(0)]

Time & Space Complexity

Time complexity: $O(m \log m + (m * α(n)))$
Space complexity:
- $O(n)$ extra space.
- $O(m)$ space depending on the sorting algorithm.

Where $m$ is the number of meetings and $n$ is the number of people.

Common Pitfalls

Ignoring the Time Ordering

Processing meetings without sorting by time first causes secrets to propagate incorrectly. The secret can only spread chronologically, so meetings must be grouped and handled in ascending time order.

Not Resetting DSU Nodes After Each Time Slot

In the Union-Find approach, failing to reset nodes that did not connect to person 0 allows stale union relationships to persist. After each time slot, any person not in the same component as person 0 must be reset to their own parent.

Using a Single Visited Set Across All Time Slots

Reusing the same visited set across different time slots prevents the secret from spreading correctly within each slot. Each time group requires a fresh visited set since a person might need to be visited again at a later time.

Missing Bidirectional Edge Construction

Only adding edges in one direction when building the adjacency list causes incomplete graph traversal. Both adj[u].append(v) and adj[v].append(u) are required since meetings are mutual.

Forgetting to Include firstPerson Initially

Initializing the secret holders with only person 0 and forgetting to add firstPerson causes incorrect results. The problem states that person 0 shares the secret with firstPerson at time 0.