-
Notifications
You must be signed in to change notification settings - Fork 0
/
2092_Find_All_People_With_Secret.py
130 lines (95 loc) · 3.88 KB
/
2092_Find_All_People_With_Secret.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
"""
2092. Find All People With Secret
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
"""
from collections import defaultdict
test0 = {
"input":{
"n": 6,
"meetings": [[1,2,5],[2,3,8],[1,5,10]],
"firstPerson": 1
},
"output": [0,1,2,3,5]
}
test1 = {
"input": {
"n": 4,
"meetings": [[3,1,3],[1,2,2],[0,3,3]],
"firstPerson": 3
},
"output": [0, 1, 3]
}
test2 = {
"input": {
"n": 5,
"meetings": [[3,4,2],[1,2,1],[2,3,1]],
"firstPerson": 1
},
"output": [0,1,2,3,4]
}
tests = [test0, test1, test2]
class Solution:
def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]:
secrets = set([0, firstPerson]) # people with secret
time_map = {} # time -- > adj list of meetings
for src, dst, t in meetings:
if t not in time_map:
time_map[t] = defaultdict(list)
time_map[t][src].append(dst)
time_map[t][dst].append(src)
def dfs(src, adj):
if src in visit:
return
visit.add(src)
secrets.add(src)
for nei in adj[src]:
dfs(nei, adj)
for t in sorted(time_map.keys()):
visit = set()
for src in time_map[t]:
if src in secrets:
dfs(src, time_map[t])
return list(secrets)
for test in tests:
print(Solution().findAllPeople(**test["input"]) == test["output"])
"""
Runtime 1580ms Beats74.83% of users with Python3
Memory 71.26MB Beats11.92% of users with Python3
"""