Sponsored
Sponsored
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.
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.
1#include <vector>
2#include <algorithm>
3#include <unordered_set>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
10 sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; });
11 vector<int> parent(n);
12 iota(parent.begin(), parent.end(), 0);
13 vector<bool> knows(n, false);
14 knows[0] = knows[firstPerson] = true;
15
16 // Find function with path compression
17 auto find = [&](int x) {
18 if (parent[x] != x)
19 parent[x] = find(parent[x]);
20 return parent[x];
21 };
22
23 // Union operation
24 auto union_sets = [&](int x, int y) {
25 int rootX = find(x);
26 int rootY = find(y);
27 if (rootX != rootY) {
28 parent[rootY] = rootX;
29 }
30 };
31
32 unordered_map<int, vector<pair<int, int>>> timeMeetings;
33 for (const auto& meeting : meetings) {
34 timeMeetings[meeting[2]].emplace_back(meeting[0], meeting[1]);
35 }
36
37 for (const auto& [time, meetingList] : timeMeetings) {
38 unordered_set<int> peopleSet;
39
40 for (const auto& [x, y] : meetingList) {
41 union_sets(x, y);
42 peopleSet.insert(x);
43 peopleSet.insert(y);
44 }
45
46 for (int person : peopleSet) {
47 if (knows[find(person)]) {
48 for (int p : peopleSet) {
49 knows[find(p)] = true;
50 }
51 break;
52 }
53 }
54
55 for (int person : peopleSet) {
56 parent[person] = person; // Reset
57 }
58 }
59
60 vector<int> result;
61 for (int i = 0; i < n; ++i) {
62 if (knows[i]) result.push_back(i);
63 }
64 return result;
65 }
66};The approach is very similar to the Python solution. We use a C++ version of union-find with path compression to efficiently manage connected components of people during the meetings. We sort the meetings by time, union the people involved, and propagate secrets accordingly. After processing a batch of meetings, we reset our union-find structure.
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.
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.
1import java.util.*;
2
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.