#2092

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Find All People With Secret

Find all people who receive a secret through meetings using graph traversal with depth-first search efficiently and correctly.

depth first search breadth first search union find graph sorting

Problem Statement

You are given an integer n representing n people labeled from 0 to n - 1. You are also given a 0-indexed array meetings where meetings[i] = [xi, yi, timei] represents a meeting between person xi and person yi at timei. Each person can attend multiple meetings at the same time, and one specific person, firstPerson, initially receives a secret from person 0 at time 0.

The secret spreads instantly during any meeting: if either participant knows the secret at the time of the meeting, the other learns it immediately. People can then share the secret in other meetings occurring at the same time. Your task is to return a list of all people who eventually know the secret after all meetings have taken place.

Examples

Example 1

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1

Output: [0,1,2,3,5]

At time 0, person 0 shares the secret with person 1. At time 5, person 1 shares the secret with person 2. At time 8, person 2 shares the secret with person 3. At time 10, person 1 shares the secret with person 5. Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3

Output: [0,1,3]

At time 0, person 0 shares the secret with person 3. At time 2, neither person 1 nor person 2 know the secret. At time 3, person 3 shares the secret with person 0 and person 1. Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1

Output: [0,1,2,3,4]

At time 0, person 0 shares the secret with person 1. At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3. Note that person 2 can share the secret at the same time as receiving it. At time 2, person 3 shares the secret with person 4. Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

Constraints

2 <= n <= 105
1 <= meetings.length <= 105
meetings[i].length == 3
0 <= xi, yi <= n - 1
xi != yi
1 <= timei <= 105
1 <= firstPerson <= n - 1

Solution Approach

Sort and Group Meetings by Time

Sort all meetings based on time to process them chronologically. Group meetings that occur at the same timestamp together, forming a temporary graph of connected people for that specific time frame.

Propagate Secret Using Graph Traversal

For each group of simultaneous meetings, traverse the temporary graph using depth-first search starting from all people who currently know the secret. Mark every reachable person as knowing the secret to ensure instantaneous propagation within that time frame.

Compile Final List

After processing all meeting groups, collect all people who have been marked as knowing the secret. This guarantees accurate results even when secrets spread through multiple simultaneous meetings across complex chains of people.

Complexity Analysis

Metric	Value
Time	O( M \log M + N)
Space	O(M + N)

Sorting the meetings takes O(M log M) where M is the number of meetings. Constructing temporary graphs and performing depth-first search over all participants takes O(N + M). Overall, time complexity is O(M log M + N) and space complexity is O(M + N).

What Interviewers Usually Probe

Notice meetings may occur simultaneously and affect multiple people instantly.
Check if depth-first search or union-find is suitable for propagating secrets efficiently.
Ask whether sorting by time is necessary to correctly model the order of secret spreading.

Common Pitfalls or Variants

Common pitfalls

Failing to account for multiple meetings occurring at the same time, which can block secret propagation.
Using breadth-first search without grouping by time, which may incorrectly spread secrets across timestamps.
Neglecting to include person 0 and firstPerson as initial secret holders in the propagation process.

Follow-up variants

Return the earliest time each person learns the secret instead of just who knows it.
Handle cases where a person can refuse to share the secret in some meetings, introducing conditional propagation.
Allow meetings to have duration intervals, requiring continuous secret propagation modeling across overlapping meetings.

FAQ

How does the secret spread to all connected people at the same meeting time?

GhostInterview models meetings as temporary graphs and uses depth-first search to propagate the secret instantly to all connected nodes within that timestamp.

Why is sorting meetings by time necessary for this problem?

Sorting ensures the secret spreads in the correct chronological order, avoiding errors where later meetings are processed before earlier ones.

Can Union-Find be applied to Find All People With Secret?

Yes, Union-Find can track connected groups for each time frame, but depth-first search provides more direct control over instantaneous secret propagation.

What should I watch for with simultaneous meetings?

Ensure all participants in simultaneous meetings are connected in a temporary graph and traverse it fully to avoid missing secret propagation.

Is there a pattern for propagating information in this problem?

Yes, this problem follows a graph traversal with depth-first search pattern, where each timestamp defines a subgraph for instant propagation.

terminal

Solution

Solution 1: Simulation + Graph Traversal

The core idea of this problem is to find all people who eventually know the secret by simulating the propagation process through meetings. We can treat each meeting as an edge in an undirected graph, where each participant is a node in the graph, and the meeting time is the "timestamp" of the edge connecting the nodes. At each time point, we traverse all meetings and use Breadth-First Search (BFS) to simulate the propagation of the secret.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def findAllPeople(
        self, n: int, meetings: List[List[int]], firstPerson: int
    ) -> List[int]:
        vis = [False] * n
        vis[0] = vis[firstPerson] = True
        meetings.sort(key=lambda x: x[2])
        i, m = 0, len(meetings)
        while i < m:
            j = i
            while j + 1 < m and meetings[j + 1][2] == meetings[i][2]:
                j += 1
            s = set()
            g = defaultdict(list)
            for x, y, _ in meetings[i : j + 1]:
                g[x].append(y)
                g[y].append(x)
                s.update([x, y])
            q = deque([u for u in s if vis[u]])
            while q:
                u = q.popleft()
                for v in g[u]:
                    if not vis[v]:
                        vis[v] = True
                        q.append(v)
            i = j + 1
        return [i for i, v in enumerate(vis) if v]

Continue Practicing

#2368 reachable nodes with restrictions #1361 validate binary tree nodes #1319 number of operations to make network connected