Problem Description

The problem asks to find all people who know a secret after a series of meetings. Initially, person 0 knows the secret and shares it with firstPerson. During each meeting [x, y, time], if either x or y knows the secret, they share it with each other. Meetings happen instantaneously; sharing can occur within the same time frame. The solution should return a list of all people who eventually know the secret.

Approach

The most efficient approach uses a combination of sorting and Breadth-First Search (BFS).

1. Sort Meetings: Sort the meetings array by time. This allows us to process meetings chronologically.

2. Iterate Through Time: Process meetings in chronological order. For meetings with the same time, process them together.

3. BFS for each time: For each set of meetings at the same time, construct a graph where nodes are people involved in those meetings and edges represent sharing the secret. Perform a BFS starting from those who already know the secret. Any person reachable during the BFS also learns the secret.

4. Update Knowledge: After processing each time, update the vis array (or equivalent data structure), indicating which people know the secret.

5. Return Result: After processing all meetings, return a list of all indices i where vis[i] is true.

Time Complexity Analysis

• Sorting meetings: O(M log M), where M is the number of meetings.
• Iterating through meetings: O(M).
• BFS for each time: In the worst case, all people could be involved in meetings at the same time, resulting in a BFS on a graph with up to N nodes and M edges (worst case when every pair of people meets at the same time). BFS is O(V + E), where V is the number of vertices and E is the number of edges; therefore, the BFS is O(N + M) in the worst case. Since we repeat BFS for each unique time, the total time for BFS would be O(T(N+M)), where T is the number of unique times.

Overall Time Complexity: O(M log M + T(N + M)). In the worst case, T could be M, which makes the complexity O(M log M + M(N+M)). However, in most cases, T is considerably smaller than M.

Space Complexity Analysis

• vis array: O(N)
• Graph (adjacency list): O(M) in the worst case (all meetings at the same time)
• Queue for BFS: O(N) in the worst case.

Overall Space Complexity: O(N + M)

Code Implementations

The code implementations below reflect the explained approach. They utilize a vis array to track which individuals know the secret, sorting the meetings by time, and then iterating through each unique time to apply a breadth-first search.

Python3:

from collections import defaultdict, deque
 
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]
 

Java:

import java.util.*;
 
class Solution {
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        boolean[] vis = new boolean[n];
        vis[0] = true;
        vis[firstPerson] = true;
        Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
        for (int i = 0; i < meetings.length;) {
            int j = i;
            while (j + 1 < meetings.length && meetings[j + 1][2] == meetings[i][2]) {
                j++;
            }
            Map<Integer, List<Integer>> graph = new HashMap<>();
            Set<Integer> nodes = new HashSet<>();
            for (int k = i; k <= j; k++) {
                int x = meetings[k][0], y = meetings[k][1];
                graph.computeIfAbsent(x, k1 -> new ArrayList<>()).add(y);
                graph.computeIfAbsent(y, k1 -> new ArrayList<>()).add(x);
                nodes.add(x);
                nodes.add(y);
            }
            Queue<Integer> q = new LinkedList<>();
            for (int node : nodes) {
                if (vis[node]) {
                    q.offer(node);
                }
            }
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph.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;
    }
}

The C++, Go, and TypeScript implementations would follow a similar structure, adapting the data structures to those languages' conventions. The core algorithm remains the same: sorting, iterative processing by time, and BFS for each time step.