Start by immediately sharing the secret from person 0 to firstPerson at time 0. Then process meetings in chronological order, building temporary graphs for simultaneous meetings, and propagate the secret using depth-first search. Return the list of all people who eventually know the secret after all meetings have concluded.
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.
How GhostInterview Helps
- GhostInterview builds the temporary graphs for simultaneous meetings automatically and highlights depth-first traversal chains.
- It detects common propagation errors where secrets fail to spread in parallel meetings or cycles.
- It provides a step-by-step simulation of secret sharing across all meetings, ensuring accurate final results.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Find All People With Secret instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find All People With Secret from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
In the 'Reachable Nodes With Restrictions' problem, find the maximum reachable nodes from node 0 in a tree while avoiding restricted nodes.
Open problem page#1361 Validate Binary Tree NodesValidate Binary Tree Nodes problem requires checking if a set of nodes forms a valid binary tree using graph traversal.
Open problem page#1319 Number of Operations to Make Network ConnectedDetermine the minimum number of operations required to connect all computers in a network with a limited number of cables.
Open problem page