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 - 1We 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.
C++
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.
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. |
Find All People With Secret - Leetcode 2092 - Python • NeetCodeIO • 15,259 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