Skip to content

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

Solutions

Solution 1: Simulation + Graph Traversal

The core idea of this problem is to find all people who eventually know the secret by simulating the propagation process through meetings. We can treat each meeting as an edge in an undirected graph, where each participant is a node in the graph, and the meeting time is the "timestamp" of the edge connecting the nodes. At each time point, we traverse all meetings and use Breadth-First Search (BFS) to simulate the propagation of the secret.

We create a boolean array \(\textit{vis}\) to record whether each person knows the secret. Initially, \(\textit{vis}[0] = \text{true}\) and \(\textit{vis}[\textit{firstPerson}] = \text{true}\), indicating that person 0 and \(\textit{firstPerson}\) already know the secret.

We first sort the meetings by time to ensure that we process meetings in the correct order during each traversal.

Next, we process each group of meetings at the same time. For each group of meetings at the same time (i.e., \(\textit{meetings}[i][2] = \textit{meetings}[i+1][2]\)), we treat them as events occurring at the same moment. For each meeting, we record the relationships between participants and add these participants to a set.

Then, we use BFS to propagate the secret. For all participants at the current time point, if any of them already know the secret, we will traverse the adjacent nodes of that participant (i.e., other participants in the meeting) through BFS and mark them as knowing the secret. This process continues to propagate until all people who can know the secret at this meeting are updated.

When all meetings are processed, we traverse the \(\textit{vis}\) array, add the IDs of all people who know the secret to the result list, and return it.

The time complexity is \(O(m \times \log m + n)\), and the space complexity is \(O(n)\), where \(m\) and \(n\) are the number of meetings and the number of experts, respectively.

 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
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]

 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
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, List.of())) {
                    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;
    }
}

 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
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;
    }
};

 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
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
}

 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
function findAllPeople(n: number, meetings: number[][], firstPerson: number): number[] {
    const vis: boolean[] = Array(n).fill(false);
    vis[0] = true;
    vis[firstPerson] = true;

    meetings.sort((x, y) => x[2] - y[2]);

    for (let i = 0, m = meetings.length; i < m; ) {
        let j = i;
        while (j + 1 < m && meetings[j + 1][2] === meetings[i][2]) {
            ++j;
        }

        const g = new Map<number, number[]>();
        const s = new Set<number>();

        for (let k = i; k <= j; ++k) {
            const x = meetings[k][0];
            const y = meetings[k][1];

            if (!g.has(x)) g.set(x, []);
            if (!g.has(y)) g.set(y, []);

            g.get(x)!.push(y);
            g.get(y)!.push(x);

            s.add(x);
            s.add(y);
        }

        const q: number[] = [];
        for (const u of s) {
            if (vis[u]) {
                q.push(u);
            }
        }

        for (const u of q) {
            for (const v of g.get(u)!) {
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }

        i = j + 1;
    }

    const ans: number[] = [];
    for (let i = 0; i < n; ++i) {
        if (vis[i]) {
            ans.push(i);
        }
    }
    return ans;
}

Comments