# Find All People With Secret **Difficulty:** HARD [External](https://leetcode.com/problems/find-all-people-with-secret) Canonical: https://scaleengineer.com/dsa/problems/find-all-people-with-secret **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find) **Data structures:** Graph --- ## Problem 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 <= 105` * `1 <= meetings.length <= 105` * `meetings[i].length == 3` * `0 <= xi, yi <= n - 1` * `xi != yi` * `1 <= timei <= 105` * `1 <= firstPerson <= n - 1` # Approaches ## Brute-Force Simulation with Repeated Scans This approach simulates the process chronologically in a straightforward but inefficient manner. It begins by sorting all meetings by their time. Then, it processes all meetings that occur at the same time together. For each distinct time step, it repeatedly scans the list of meetings for that time, spreading the secret from those who know it to those who don't. This iterative scanning continues until a full pass results in no new person learning the secret, ensuring the instantaneous spread is modeled correctly before moving to the next time step. **Time:** O(M log M + Σ(M_t * P_t)) where `M` is the total number of meetings, `M_t` is the number of meetings at time `t`, and `P_t` is the number of people involved at time `t`. In the worst-case scenario where all meetings happen at the same time and form a long chain, this can degrade to `O(M log M + M*N)`, which is too slow for the given constraints. · **Space:** O(N + M) in the worst case, where `N` is the number of people and `M` is the number of meetings. `O(N)` for the `knowsSecret` array and `O(M)` to store the list of meetings happening at the same time if all meetings occur simultaneously. **Pros:** Conceptually simple and easy to follow the logic.; Directly simulates the process described in the problem statement. **Cons:** The time complexity is very high due to the nested loop structure for handling meetings at the same time. For a time step with `M_t` meetings and `P_t` participants, the inner loop could run up to `P_t` times, leading to a complexity of `O(M_t * P_t)` for that step.; This approach will likely result in a 'Time Limit Exceeded' error on larger test cases. ### Explanation The core idea is to handle the events in the order they happen. Since secrets can spread instantly among multiple people meeting at the same time, we must process all meetings at a given time `t` as a single event. This brute-force method does this by repeatedly iterating over the meetings at time `t`. In each iteration, it checks if any new person can learn the secret. If so, it updates their status and repeats the process. This continues until a state of equilibrium is reached for time `t`, where no more secrets can be shared. Then, it moves on to the next distinct meeting time. ```java import java.util.*; class Solution { public List findAllPeople(int n, int[][] meetings, int firstPerson) { Arrays.sort(meetings, (a, b) -> a[2] - b[2]); boolean[] knowsSecret = new boolean[n]; knowsSecret[0] = true; knowsSecret[firstPerson] = true; int i = 0; while (i < meetings.length) { int currentTime = meetings[i][2]; List sameTimeMeetings = new ArrayList<>(); int j = i; while (j < meetings.length && meetings[j][2] == currentTime) { sameTimeMeetings.add(meetings[j]); j++; } boolean newSecretSpread = true; while (newSecretSpread) { newSecretSpread = false; for (int[] meeting : sameTimeMeetings) { int p1 = meeting[0]; int p2 = meeting[1]; if (knowsSecret[p1] && !knowsSecret[p2]) { knowsSecret[p2] = true; newSecretSpread = true; } if (knowsSecret[p2] && !knowsSecret[p1]) { knowsSecret[p1] = true; newSecretSpread = true; } } } i = j; } List result = new ArrayList<>(); for (int p = 0; p < n; p++) { if (knowsSecret[p]) { result.add(p); } } return result; } } ``` ### Algorithm - Initialize a boolean array `knowsSecret` of size `n`, marking person `0` and `firstPerson` as knowing the secret. - Sort the `meetings` array based on their time in ascending order. - Iterate through the sorted meetings, grouping them by their meeting time. - For each group of meetings occurring at the same time `t`: - Create a temporary list of these meetings, `meetings_t`. - Use a flag, `newSecretSpread`, and loop until a full pass over `meetings_t` results in no new people learning the secret. - In each pass, iterate through every meeting `(x, y)` in `meetings_t`. - If `knowsSecret[x]` is true and `knowsSecret[y]` is false, set `knowsSecret[y]` to true and set `newSecretSpread` to true. - Do the same if `y` knows the secret and `x` does not. - After iterating through all time groups, collect the indices of all people for whom `knowsSecret` is true and return them as a list. ## Chronological Simulation with Graph Traversal (BFS) This approach improves upon the brute-force method by using a more efficient technique to handle the instantaneous spread of the secret at each time step. After sorting meetings by time, it processes them in batches. For each time, it constructs an explicit graph where people are nodes and meetings are edges. Then, it uses a graph traversal algorithm like Breadth-First Search (BFS) to find all people connected to someone who already knew the secret. This avoids the inefficient repeated scanning and correctly identifies all newly informed people in a single pass for that time step. **Time:** O(M log M). Sorting takes `O(M log M)`. The subsequent processing involves iterating through each meeting once to build graphs and once for traversal. The total work for all graph operations is `O(M)`. Thus, the sorting step dominates. · **Space:** O(N + M). `O(N)` for `knowsSecret` array and `O(M)` for the adjacency list in the worst case where all meetings happen at the same time. **Pros:** Significantly more efficient than the brute-force approach.; Correctly and efficiently models the instantaneous spread of information at each time step.; The logic is clear and relies on standard graph traversal algorithms. **Cons:** Requires building a new graph (adjacency list) for each distinct meeting time, which can have some overhead, especially if there are many unique meeting times. ### Explanation The main optimization here is to recognize that for a given time `t`, the problem of spreading the secret is equivalent to finding all reachable nodes in a graph from a set of source nodes. The people who already know the secret are the sources. - **Sorting**: First, we sort meetings by time to process events chronologically. `O(M log M)`. - **Grouping**: We iterate through the sorted meetings and group them by time. - **Graph Building & Traversal**: For each time group, we build an adjacency list for all people involved. Then, we initialize a queue with all people who are in this time's meetings and already know the secret. A standard BFS traversal from these initial nodes will find all connected people. All people visited by the BFS will learn the secret. The total work for graph building and traversal across all time steps is proportional to the total number of meetings and participants, which is `O(M)`. ```java import java.util.*; class Solution { public List findAllPeople(int n, int[][] meetings, int firstPerson) { Arrays.sort(meetings, (a, b) -> a[2] - b[2]); boolean[] knowsSecret = new boolean[n]; knowsSecret[0] = true; knowsSecret[firstPerson] = true; int i = 0; while (i < meetings.length) { int currentTime = meetings[i][2]; int j = i; while (j + 1 < meetings.length && meetings[j + 1][2] == currentTime) { j++; } Map> adj = new HashMap<>(); Set participants = new HashSet<>(); for (int k = i; k <= j; k++) { int p1 = meetings[k][0]; int p2 = meetings[k][1]; adj.computeIfAbsent(p1, val -> new ArrayList<>()).add(p2); adj.computeIfAbsent(p2, val -> new ArrayList<>()).add(p1); participants.add(p1); participants.add(p2); } Queue queue = new LinkedList<>(); for (int p : participants) { if (knowsSecret[p]) { queue.offer(p); } } Set visitedInTimeStep = new HashSet<>(queue); while (!queue.isEmpty()) { int person = queue.poll(); for (int neighbor : adj.getOrDefault(person, new ArrayList<>())) { if (!visitedInTimeStep.contains(neighbor)) { knowsSecret[neighbor] = true; queue.offer(neighbor); visitedInTimeStep.add(neighbor); } } } i = j + 1; } List result = new ArrayList<>(); for (int p = 0; p < n; p++) { if (knowsSecret[p]) { result.add(p); } } return result; } } ``` ### Algorithm - Initialize a boolean array `knowsSecret` of size `n`, marking person `0` and `firstPerson` as true. - Sort the `meetings` array by time. - Iterate through the sorted meetings, processing them in chunks that share the same meeting time. - For each time `t`: - Identify all meetings and unique participants for this time. - Build an adjacency list to represent the graph of interactions at time `t`. - Create a queue for BFS and add all participants of time `t` who already know the secret. - Perform a BFS starting from these people. Traverse the graph for time `t`. - For every person visited during the BFS, mark them in the `knowsSecret` array as true. - After processing all time chunks, collect and return the list of people who know the secret. ## Optimized Chronological Simulation with Union-Find This approach is a highly optimized version that uses a Union-Find (Disjoint Set Union) data structure to efficiently manage connectivity. Like the other approaches, it processes meetings chronologically. For each time step, instead of building an explicit graph, it uses `union` operations to group everyone involved in meetings into connected components. If any member of a component already knows the secret, the entire component learns it. This method is particularly well-suited for dynamic connectivity problems and offers excellent performance. **Time:** O(M log M + M * α(N)), where `α(N)` is the extremely slow-growing inverse Ackermann function. Sorting takes `O(M log M)`. The loop over meetings involves Union-Find operations, which take `O(M * α(N))` time in total. This is asymptotically the best performance. · **Space:** O(N + P_t), where `P_t` is the number of participants at the busiest time step. `O(N)` for `knowsSecret` and the Union-Find structure. `O(P_t)` for the participants set and map. **Pros:** The most efficient approach in terms of time complexity due to the near-constant time operations of the Union-Find data structure.; Elegant solution for modeling dynamic connectivity. **Cons:** The implementation can be slightly more complex than the BFS approach, particularly in managing the state of components and propagating the secret.; Requires careful implementation to ensure the temporary nature of connections is handled correctly (e.g., by re-initializing for each time step or resetting specific nodes). ### Explanation The Union-Find data structure is perfect for determining connected components dynamically. For each time step, we can model the meetings as a set of connections. 1. **Sort Meetings**: As before, sort meetings by time. `O(M log M)`. 2. **Process by Time**: Group meetings by time. 3. **Union-Find for each Time Step**: For each time `t`, we determine the connected components of people meeting at that time. - We can use a fresh Union-Find structure for each time step or reset the state of participants after processing. - We iterate through the meetings at time `t` and call `union(p1, p2)` for each meeting. - After all unions, we have sets representing the connected components. We then need to propagate the secret. We can do this in two passes over the participants: first, identify which components contain at least one person who already knows the secret. Second, update all members of those components to know the secret. This avoids building an explicit adjacency list and traversing it, often leading to a faster runtime with lower constant factors. ```java import java.util.*; class Solution { public List findAllPeople(int n, int[][] meetings, int firstPerson) { Arrays.sort(meetings, (a, b) -> a[2] - b[2]); boolean[] knowsSecret = new boolean[n]; knowsSecret[0] = true; knowsSecret[firstPerson] = true; int i = 0; while (i < meetings.length) { int currentTime = meetings[i][2]; int j = i; while (j + 1 < meetings.length && meetings[j + 1][2] == currentTime) { j++; } UnionFind uf = new UnionFind(n); Set participants = new HashSet<>(); for (int k = i; k <= j; k++) { int p1 = meetings[k][0]; int p2 = meetings[k][1]; uf.union(p1, p2); participants.add(p1); participants.add(p2); } Map groupHasSecret = new HashMap<>(); for (int p : participants) { if (knowsSecret[p]) { int root = uf.find(p); groupHasSecret.put(root, true); } } for (int p : participants) { int root = uf.find(p); if (groupHasSecret.getOrDefault(root, false)) { knowsSecret[p] = true; } } i = j + 1; } List result = new ArrayList<>(); for (int p = 0; p < n; p++) { if (knowsSecret[p]) { result.add(p); } } return result; } class UnionFind { private int[] parent; public UnionFind(int n) { parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; } public int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) parent[rootI] = rootJ; } } } ``` ### Algorithm - Initialize a boolean array `knowsSecret` of size `n`, marking person `0` and `firstPerson` as true. - Sort the `meetings` array by time. - Iterate through the sorted meetings, processing chunks with the same time `t`. - For each time chunk: - Collect all unique participants `P_t`. - Create a Union-Find data structure over `n` people. - For each meeting `(x, y)` at time `t`, perform a `union(x, y)` operation. This groups all connected people into disjoint sets. - After forming the sets, identify which sets contain a person who already knew the secret. This can be done by iterating through `P_t` and using a map or set to mark the roots of components that have a secret. - Iterate through `P_t` again. If a person `p` belongs to a component that has the secret, update `knowsSecret[p]` to true. - After processing all meetings, collect and return the list of people who know the secret. # Solutions ### Java ```java class Solution { public List findAllPeople(int n, int[][] meetings, int firstPerson) { boolean[] vis = new boolean[n]; vis[0] = true; vis[firstPerson] = true; int m = meetings.length; Arrays.sort(meetings, Comparator.comparingInt(a->a[2])); for (int i = 0; i < m;) { int j = i; for (; j + 1 < m && meetings[j + 1][2] == meetings[i][2]; ++j) ; Map> g = new HashMap<>(); Set s = new HashSet<>(); for (int k = i; k <= j; ++k) { int x = meetings[k][0], y = meetings[k][1]; g.computeIfAbsent(x, key->new ArrayList<>()).add(y); g.computeIfAbsent(y, key->new ArrayList<>()).add(x); s.add(x); s.add(y); } Deque q = new ArrayDeque<>(); for (int u : s) { if (vis[u]) { q.offer(u); } } while (!q.isEmpty()) { int u = q.poll(); for (int v : g.getOrDefault(u, Collections.emptyList())) { if (!vis[v]) { vis[v] = true; q.offer(v); } } } i = j + 1; } List ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (vis[i]) { ans.add(i); } } return ans; } } ``` ### CPP ```cpp class Solution { public: vector findAllPeople(int n, vector> &meetings, int firstPerson) { vector vis(n); vis[0] = vis[firstPerson] = true; sort(meetings.begin(), meetings.end(), [&](const auto &x, const auto &y) { return x[2] < y[2]; }); for (int i = 0, m = meetings.size(); i < m;) { int j = i; for (; j + 1 < m && meetings[j + 1][2] == meetings[i][2]; ++j) ; unordered_map> g; unordered_set s; for (int k = i; k <= j; ++k) { int x = meetings[k][0], y = meetings[k][1]; g[x].push_back(y); g[y].push_back(x); s.insert(x); s.insert(y); } queue q; for (int u : s) if (vis[u]) q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (!vis[v]) { vis[v] = true; q.push(v); } } } i = j + 1; } vector ans; for (int i = 0; i < n; ++i) if (vis[i]) ans.push_back(i); return ans; } }; ``` ### Python ```python 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] ```