Welcome to Subscribe On Youtube
2092. Find All People With Secret
Description
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 - 1
Solutions
BFS.
-
class Solution { public List<Integer> 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<Integer, List<Integer>> g = new HashMap<>(); Set<Integer> 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<Integer> 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<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { if (vis[i]) { ans.add(i); } } return ans; } } -
class Solution { public: vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) { vector<bool> 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<int, vector<int>> g; unordered_set<int> 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<int> 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<int> ans; for (int i = 0; i < n; ++i) if (vis[i]) ans.push_back(i); return ans; } }; -
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] -
func findAllPeople(n int, meetings [][]int, firstPerson int) []int { vis := make([]bool, n) vis[0], vis[firstPerson] = true, true sort.Slice(meetings, func(i, j int) bool { return meetings[i][2] < meetings[j][2] }) for i, j, m := 0, 0, len(meetings); i < m; i = j + 1 { j = i for j+1 < m && meetings[j+1][2] == meetings[i][2] { j++ } g := map[int][]int{} s := map[int]bool{} for _, e := range meetings[i : j+1] { x, y := e[0], e[1] g[x] = append(g[x], y) g[y] = append(g[y], x) s[x], s[y] = true, true } q := []int{} for u := range s { if vis[u] { q = append(q, u) } } for len(q) > 0 { u := q[0] q = q[1:] for _, v := range g[u] { if !vis[v] { vis[v] = true q = append(q, v) } } } } var ans []int for i, v := range vis { if v { ans = append(ans, i) } } return ans } -
function findAllPeople(n: number, meetings: number[][], firstPerson: number): number[] { let parent: Array<number> = Array.from({ length: n + 1 }, (v, i) => i); parent[firstPerson] = 0; function findParent(index: number): number { if (parent[index] != index) parent[index] = findParent(parent[index]); return parent[index]; } let map = new Map<number, Array<Array<number>>>(); for (let meeting of meetings) { const time = meeting[2]; let members: Array<Array<number>> = map.get(time) || new Array(); members.push(meeting); map.set(time, members); } const times = [...map.keys()].sort((a, b) => a - b); for (let time of times) { // round 1 for (let meeting of map.get(time)) { let [a, b] = meeting; if (!parent[findParent(a)] || !parent[findParent(b)]) { parent[findParent(a)] = 0; parent[findParent(b)] = 0; } parent[findParent(a)] = parent[findParent(b)]; } // round 2 for (let meeting of map.get(time)) { let [a, b] = meeting; if (!parent[findParent(a)] || !parent[findParent(b)]) { parent[findParent(a)] = 0; parent[findParent(b)] = 0; } else { parent[a] = a; parent[b] = b; } } } let ans = new Array<number>(); for (let i = 0; i <= n; i++) { if (!parent[findParent(i)]) { ans.push(i); } } return ans; }