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.
1def findAllPeople(n, meetings, firstPerson):
2 meetings.sort(key=lambda x: x[2])
3 parent = list(range(n))
4 knows = [False] * n
5 knows[0] = knows[firstPerson] = True
6
7 def find(x):
8 if parent[x] != x:
9 parent[x] = find(parent[x])
10 return parent[x]
11
12 def union(x, y):
13 rootX, rootY = find(x), find(y)
14 if rootX != rootY:
15 parent[rootY] = rootX
16
17 time_meeting_map = {}
18 for x, y, time in meetings:
19 if time not in time_meeting_map:
20 time_meeting_map[time] = []
21 time_meeting_map[time].append((x, y))
22
23 for time in sorted(time_meeting_map):
24 groups = []
25 for x, y in time_meeting_map[time]:
26 union(x, y)
27 groups.append(x)
28 groups.append(y)
29
30 temp_set = set(groups)
31
32 for person in temp_set:
33 root = find(person)
34 if knows[root]:
35 for p in temp_set:
36 knows[find(p)] = True
37
38 for person in temp_set:
39 parent[person] = person
40 return [i for i in range(n) if knows[i]]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.
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.
1const findAllPeople = (n, meetings, firstPerson
We translate the algorithm to JavaScript, where a similar BFS process is used to spread the secret among the people. Sorted meetings are processed chronologically, and a queue handles people sharing the secret. If someone in a meeting knows the secret, it gets shared. Finally, we check who knows the secret.