You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [xi, yi, timei] indicates that person xi and person yi have a meeting at timei. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.
Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person xi has the secret at timei, then they will share the secret with person yi, and vice versa.
The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.
Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.
Example 1:
Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1 Output: [0,1,2,3,5] Explanation: 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] Explanation: 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] Explanation: 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 <= 1051 <= meetings.length <= 105meetings[i].length == 30 <= xi, yi <= n - 1xi != yi1 <= timei <= 1051 <= firstPerson <= n - 1Problem Overview: You have n people and a list of meetings [x, y, time]. Person 0 initially knows a secret and shares it with firstPerson. Whenever two people meet, the secret spreads instantly if either participant already knows it. The challenge is handling meetings that occur at the same time while ensuring the secret only spreads through valid chains.
Approach 1: Union-Find with Time Reset (Sorting + Disjoint Set) (Time: O(m log m), Space: O(n))
Sort all meetings by time so you process them chronologically. For meetings occurring at the same timestamp, temporarily connect participants using a Union-Find structure. If a connected component contains someone who already knows the secret (initially person 0 and firstPerson), the secret propagates to the entire component. After finishing a time block, reset connections for groups that are not connected to the secret holder so the secret cannot incorrectly travel to later meetings. This works because meetings at the same time form temporary communication networks that should not persist beyond that timestamp.
This approach relies heavily on the Union Find data structure for near-constant connectivity checks. Sorting ensures chronological correctness. Path compression and union by rank keep operations efficient even when the number of meetings is large.
Approach 2: Graph Traversal Per Time Block (BFS/DFS) (Time: O(m log m + m), Space: O(m))
Another way to model the problem is as a series of small graphs formed by meetings that occur at the same time. Start by sorting meetings by time. For each timestamp, build an adjacency list connecting everyone who meets during that moment. Then run a traversal (either BFS or DFS) starting from participants who already know the secret. Anyone reachable within that time-block graph learns the secret as well.
After finishing traversal for that timestamp, discard the graph and move to the next time group. This prevents information from leaking through edges that should only exist temporarily. The traversal naturally fits standard Breadth-First Search or Depth-First Search patterns used in graph problems.
Recommended for interviews: The Union-Find approach is usually the expected optimal solution because it handles dynamic connectivity efficiently and demonstrates strong understanding of disjoint-set structures. Graph traversal per time block is also valid and often easier to reason about during implementation. Interviewers typically want to see that you first recognize the need to process meetings in chronological order, then model simultaneous meetings as temporary connectivity groups.
We sort the meetings by time and use the Union-Find (Disjoint Set) data structure to manage which groups of people know the secret at each point in time. Initially, person 0 knows the secret and shares it with the firstPerson at time 0. As the meetings progress, we perform union operations on people involved in meetings at the same time, and for each new time, we propagate the secret within the connected components.
We first sort the meetings by their time. For each group of meetings happening at the same time, we union the respective people and then check if any of them know the secret. If they do, we propagate the knowledge to everyone in the same connected component (group of people who can share the secret due to the meetings). Finally, we reset the connected components and check who knows the secret by the end of all meetings.
The time complexity is O((n + m) log m) where n is the number of people and m is the number of meetings. This accounts for sorting the meetings and performing union-find operations. The space complexity is O(n) due to the storage required for parent tracking and knowledge status.
We can view the people and their meetings as a graph where people are nodes and meetings are edges with timestamps. We perform Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the graph, starting from person 0 and the initially known first person, propagating secret knowledge among connected nodes (people) within allowable time frames.
In this approach, we first sort the meetings by time, then use a BFS to traverse starting from person 0 and the firstPerson. As we go through the sorted meetings, we use a queue to track who currently knows the secret. If a person is in a meeting pair with someone else who knows the secret, they learn it too. We keep propagating this knowledge as we traverse.
Java
JavaScript
The time complexity here is O(m log m + m) due to sorting and BFS traversal, where m is the number of meetings. Space complexity is O(n + m) to hold our data structures for tracking secret knowledge.
| Approach | Complexity |
|---|---|
| Union-Find Approach | The time complexity is O((n + m) log m) where n is the number of people and m is the number of meetings. This accounts for sorting the meetings and performing union-find operations. The space complexity is O(n) due to the storage required for parent tracking and knowledge status. |
| Graph Traversal (BFS/DFS) Approach | The time complexity here is O(m log m + m) due to sorting and BFS traversal, where m is the number of meetings. Space complexity is O(n + m) to hold our data structures for tracking secret knowledge. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find with Time Reset | O(m log m) | O(n) | Best general solution for interviews. Efficient connectivity tracking when meetings occur in time batches. |
| Graph Traversal per Time Block (BFS/DFS) | O(m log m + m) | O(m) | Useful when you prefer explicit graph modeling and traversal logic for each timestamp. |
Find All People With Secret - Leetcode 2092 - Python • NeetCodeIO • 17,384 views views
Watch 9 more video solutions →Practice Find All People With Secret with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor