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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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 <= 10^5
  • 1 <= meetings.length <= 10^5
  • meetings[i].length == 3
  • 0 <= xi, yi <= n - 1
  • xi != yi
  • 1 <= timei <= 10^5
  • 1 <= firstPerson <= n - 1

Solution

Method 1 – Union-Find by Time Groups

Intuition

Meetings at the same time can spread the secret instantly among all connected people. We can process meetings in order of time, and for each time group, use union-find to connect people. After each group, only keep the secret for those connected to someone who already knows it.

Approach

  1. Sort meetings by time.
  2. For each group of meetings at the same time:
    • Use union-find to connect all people in the group.
    • For each connected component, if any person in it knows the secret, all in the component know it.
    • After the group, reset the union-find for only those who learned the secret.
  3. Start with person 0 and firstPerson knowing the secret.
  4. Return all people who know the secret after all meetings.

Code

 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

class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        vector<int> knows(n, 0);
        knows[0] = knows[firstPerson] = 1;
        sort(meetings.begin(), meetings.end(), [](auto& a, auto& b){ return a[2] < b[2]; });
        int m = meetings.size();
        for (int i = 0; i < m; ) {
            int t = meetings[i][2], j = i;
            unordered_map<int, int> par;
            function<int(int)> find = [&](int x) {
                if (!par.count(x)) par[x] = x;
                if (par[x] != x) par[x] = find(par[x]);
                return par[x];
            };
            for (; j < m && meetings[j][2] == t; ++j) {
                int x = meetings[j][0], y = meetings[j][1];
                par[find(x)] = find(y);
            }
            unordered_map<int, vector<int>> groups;
            for (int k = i; k < j; ++k) {
                int x = meetings[k][0], y = meetings[k][1];
                groups[find(x)].push_back(x);
                groups[find(y)].push_back(y);
            }
            for (auto& [root, group] : groups) {
                bool hasSecret = false;
                for (int x : group) if (knows[x]) { hasSecret = true; break; }
                if (hasSecret) for (int x : group) knows[x] = 1;
            }
            i = j;
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i) if (knows[i]) ans.push_back(i);
        return ans;
    }
};
 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

func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
    knows := make([]bool, n)
    knows[0], knows[firstPerson] = true, true
    sort.Slice(meetings, func(i, j int) bool { return meetings[i][2] < meetings[j][2] })
    for i := 0; i < len(meetings); {
        t := meetings[i][2]
        par := map[int]int{}
        var find func(int) int
        find = func(x int) int {
            if _, ok := par[x]; !ok { par[x] = x }
            if par[x] != x { par[x] = find(par[x]) }
            return par[x]
        }
        j := i
        for ; j < len(meetings) && meetings[j][2] == t; j++ {
            x, y := meetings[j][0], meetings[j][1]
            par[find(x)] = find(y)
        }
        groups := map[int][]int{}
        for k := i; k < j; k++ {
            x, y := meetings[k][0], meetings[k][1]
            groups[find(x)] = append(groups[find(x)], x)
            groups[find(y)] = append(groups[find(y)], y)
        }
        for _, group := range groups {
            hasSecret := false
            for _, x := range group {
                if knows[x] { hasSecret = true; break }
            }
            if hasSecret {
                for _, x := range group { knows[x] = true }
            }
        }
        i = j
    }
    ans := []int{}
    for i, v := range knows {
        if v { ans = append(ans, i) }
    }
    return ans
}
 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

class Solution {
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        boolean[] knows = new boolean[n];
        knows[0] = knows[firstPerson] = true;
        Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
        for (int i = 0; i < meetings.length; ) {
            int t = meetings[i][2], j = i;
            Map<Integer, Integer> par = new HashMap<>();
            java.util.function.Function<Integer, Integer> find = new java.util.function.Function<>() {
                public Integer apply(Integer x) {
                    if (!par.containsKey(x)) par.put(x, x);
                    if (!par.get(x).equals(x)) par.put(x, apply(par.get(x)));
                    return par.get(x);
                }
            };
            for (; j < meetings.length && meetings[j][2] == t; ++j) {
                int x = meetings[j][0], y = meetings[j][1];
                par.put(find.apply(x), find.apply(y));
            }
            Map<Integer, List<Integer>> groups = new HashMap<>();
            for (int k = i; k < j; ++k) {
                int x = meetings[k][0], y = meetings[k][1];
                groups.computeIfAbsent(find.apply(x), z -> new ArrayList<>()).add(x);
                groups.computeIfAbsent(find.apply(y), z -> new ArrayList<>()).add(y);
            }
            for (var group : groups.values()) {
                boolean hasSecret = false;
                for (int x : group) if (knows[x]) { hasSecret = true; break; }
                if (hasSecret) for (int x : group) knows[x] = true;
            }
            i = j;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) if (knows[i]) ans.add(i);
        return ans;
    }
}
 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

class Solution {
    fun findAllPeople(n: Int, meetings: Array<IntArray>, firstPerson: Int): List<Int> {
        val knows = BooleanArray(n)
        knows[0] = true; knows[firstPerson] = true
        meetings.sortBy { it[2] }
        var i = 0
        while (i < meetings.size) {
            val t = meetings[i][2]
            val par = mutableMapOf<Int, Int>()
            fun find(x: Int): Int {
                if (par.getOrDefault(x, x) != x) par[x] = find(par[x]!!)
                return par.getOrDefault(x, x)
            }
            var j = i
            while (j < meetings.size && meetings[j][2] == t) {
                val (x, y) = meetings[j]
                par[find(x)] = find(y)
                j++
            }
            val groups = mutableMapOf<Int, MutableList<Int>>()
            for (k in i until j) {
                val (x, y) = meetings[k]
                groups.getOrPut(find(x)) { mutableListOf() }.add(x)
                groups.getOrPut(find(y)) { mutableListOf() }.add(y)
            }
            for (group in groups.values) {
                if (group.any { knows[it] }) group.forEach { knows[it] = true }
            }
            i = j
        }
        return knows.withIndex().filter { it.value }.map { it.index }
    }
}
 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

class Solution:
    def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]:
        from collections import defaultdict
        knows = [False] * n
        knows[0] = knows[firstPerson] = True
        meetings.sort(key=lambda x: x[2])
        i = 0
        while i < len(meetings):
            t = meetings[i][2]
            par = {}
            def find(x):
                if x not in par:
                    par[x] = x
                if par[x] != x:
                    par[x] = find(par[x])
                return par[x]
            j = i
            while j < len(meetings) and meetings[j][2] == t:
                x, y = meetings[j][0], meetings[j][1]
                par[find(x)] = find(y)
                j += 1
            groups = defaultdict(list)
            for k in range(i, j):
                x, y = meetings[k][0], meetings[k][1]
                groups[find(x)].append(x)
                groups[find(y)].append(y)
            for group in groups.values():
                if any(knows[x] for x in group):
                    for x in group:
                        knows[x] = True
            i = j
        return [i for i, v in enumerate(knows) if v]
 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

use std::collections::HashMap;
impl Solution {
    pub fn find_all_people(n: i32, mut meetings: Vec<Vec<i32>>, first_person: i32) -> Vec<i32> {
        let n = n as usize;
        let mut knows = vec![false; n];
        knows[0] = true;
        knows[first_person as usize] = true;
        meetings.sort_by_key(|x| x[2]);
        let mut i = 0;
        while i < meetings.len() {
            let t = meetings[i][2];
            let mut par = HashMap::new();
            fn find(par: &mut HashMap<i32, i32>, x: i32) -> i32 {
                let p = *par.get(&x).unwrap_or(&x);
                if p != x {
                    let root = find(par, p);
                    par.insert(x, root);
                    root
                } else {
                    x
                }
            }
            let mut j = i;
            while j < meetings.len() && meetings[j][2] == t {
                let x = meetings[j][0];
                let y = meetings[j][1];
                let px = find(&mut par, x);
                let py = find(&mut par, y);
                par.insert(px, py);
                j += 1;
            }
            let mut groups: HashMap<i32, Vec<i32>> = HashMap::new();
            for k in i..j {
                let x = meetings[k][0];
                let y = meetings[k][1];
                let px = find(&mut par, x);
                let py = find(&mut par, y);
                groups.entry(px).or_default().push(x);
                groups.entry(py).or_default().push(y);
            }
            for group in groups.values() {
                if group.iter().any(|&x| knows[x as usize]) {
                    for &x in group {
                        knows[x as usize] = true;
                    }
                }
            }
            i = j;
        }
        (0..n).filter(|&i| knows[i]).map(|i| i as i32).collect()
    }
}
 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

class Solution {
    findAllPeople(n: number, meetings: number[][], firstPerson: number): number[] {
        const knows = Array(n).fill(false);
        knows[0] = knows[firstPerson] = true;
        meetings.sort((a, b) => a[2] - b[2]);
        let i = 0;
        while (i < meetings.length) {
            const t = meetings[i][2];
            const par = new Map<number, number>();
            const find = (x: number): number => {
                if (!par.has(x)) par.set(x, x);
                if (par.get(x)! !== x) par.set(x, find(par.get(x)!));
                return par.get(x)!;
            };
            let j = i;
            for (; j < meetings.length && meetings[j][2] === t; ++j) {
                const [x, y] = meetings[j];
                par.set(find(x), find(y));
            }
            const groups = new Map<number, number[]>();
            for (let k = i; k < j; ++k) {
                const [x, y] = meetings[k];
                const px = find(x), py = find(y);
                if (!groups.has(px)) groups.set(px, []);
                if (!groups.has(py)) groups.set(py, []);
                groups.get(px)!.push(x);
                groups.get(py)!.push(y);
            }
            for (const group of groups.values()) {
                if (group.some(x => knows[x])) group.forEach(x => knows[x] = true);
            }
            i = j;
        }
        return knows.map((v, i) => v ? i : -1).filter(x => x !== -1);
    }
}

Complexity

  • ⏰ Time complexity: O(m log m + m α(n)), where m is the number of meetings and n is the number of people. Sorting and union-find operations are efficient.
  • 🧺 Space complexity: O(n + m), for the union-find structures and result.