2092. Find All People With Secret
Problem Description
The LeetCode problem presents a scenario in which a group of n
people, numbered from 0
to n-1
, are engaging in a series of meetings. Each meeting is represented by a triplet [xi, yi, timei]
, signifying that person xi
has a meeting with person yi
at timei
. One crucial detail is that people may participate in several meetings at the same time. In this setting, there is a secret that originates with person 0
and is shared with firstPerson
at the initial time of 0
. This secret spreads through the meetings: if any person in a meeting knows the secret, they will share it with the other person in that meeting at the said time. The secret sharing is instantaneous, which means a person can receive and pass on the secret within the same time frame across different meetings.
The objective is to determine which persons will know the secret after all meetings have concluded. The resulting list can be returned in any order.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here is a step-by-step walkthrough:
Is it a graph?
- Yes: The problem involves people (nodes) who can meet (edges represent these meetings), sharing secrets over time, represented by edges with times as attributes.
Is it a tree?
- No: This graph may have cycles since people can meet multiple other people over time, not forming a hierarchy.
Is the problem related to directed acyclic graphs (DAGs)?
- No: This problem involves potentially cyclic interactions between people; it's not inherently directed nor acyclic.
Is the problem related to shortest paths?
- No: The problem's focus is on determining which people know a secret by the end of all meetings, not about finding the shortest routes between nodes.
Does the problem involve connectivity?
- Yes: We're interested in whether a person is connected to the initial secret bearer(s) through meetings schedules and sequences.
Does the problem have small constraints?
- No: Given the problem's complexity and possible significant number of meetings and participants, a highly efficient algorithm is needed.
Conclusion: The flowchart directs us to consider either DFS or BFS for such connectivity problems where the graph is potentially large. In this particular case, Depth-First Search (DFS) would be highly suitable to explore connections and update states (secret holders) as new meetups are examined, making it the right choice given the graph nature of the problem.
Intuition
The key to solving this problem lies in understanding how information (the secret) flows through the network of meetings based on time and the connections between people. We want to track the spreading of the secret efficiently, and a Breadth-First Search (BFS) approach lends itself well to this situation. It allows us to simulate the process of sharing the secret during each time frame.
To execute the BFS approach:
- We first assume that only person
0
andfirstPerson
know the secret initially. - We'll need to process the meetings in chronological order, which is why the meetings list is sorted by time.
- For each unique time frame, we establish a subgraph of meetings that contribute to the sharing of the secret during that particular time. This subgraph contains nodes (people) and edges (meetings) where secret sharing may occur.
- We initialize our BFS queue with persons known to have the secret at the beginning of that time frame. As we share the secret within the subgraph, we mark each recipient as someone who knows the secret (
vis
array). - We perform a BFS across the subgraph, sharing the secret with individuals connected to those who already know the secret.
- Upon completing the BFS for the subgraph, we move on to the next unique time frame and repeat this process.
- After reviewing all time frames, we then have a finalized list of individuals (
vis
) who eventually know the secret, which is returned as our solution.
The implementation locates each clique of interconnected meetings at a time "t" and applies BFS within it, thereby capturing the essence of instantaneous secret sharing within a confined temporal scope. This approach ensures that the secret is shared with all participants reachable according to the rules of secret transmission as laid out in the problem description.
Learn more about Depth-First Search, Breadth-First Search, Union Find, Graph and Sorting patterns.
Solution Approach
The provided solution adopts a Breadth-First Search (BFS) strategy to traverse through the network of meetings and spread the secret. Here's a walkthrough of the implementation:
-
The
vis
array, which stands for "visited," is used to keep track of the people who know the secret. It is initialized withFalse
values for each person and set toTrue
for person0
andfirstPerson
, who know the secret initially. -
The
meetings
are sorted by their time to ensure that the BFS is carried out in chronological order. -
A while-loop is used to process meetings in blocks that share the same time
t
. The variablesi
andj
help identify the start and end index of meetings happening at the same time. -
A set
s
is used to identify unique people participating in meetings at the current timet
, while adefaultdict
of lists, namedg
, is formed to create an adjacency list representing connections (meetings) between people. -
Once the subgraph of meetings for time
t
is established, a BFS is initiated only on individuals from this list whom we already know possess the secret (for u in s if vis[u]
). This is done by using adeque
to efficiently handle the BFS queue operations. -
The BFS proceeds by popping a person
u
from the left of the queue and iterating over all the peoplev
they have meetings with at the current timet
. If personv
has not yet received the secret (if not vis[v]
), we mark them as having received it (vis[v] = True
) and append them to the queue to continue spreading the secret. -
Once the queue is empty, it means the BFS has covered all reachable individuals within that specific time frame and any person in
vis
who isTrue
now knows the secret. -
The outer while-loop continues to the next block of meetings by updating
i
toj + 1
, and the process repeats until all meetings are processed. -
Finally, a list comprehension is used to collect all indices
i
of thevis
array that areTrue
, indicating these people know the secret after all the meetings, and this list is returned.
By utilizing BFS in combination with chronological processing and set operations, the solution efficiently resolves the propagation challenge posed by the problem, adhering to the constraint of instant secret sharing.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Assuming we have n = 4
people and the following meetings array:
meetings = [[0, 1, 1], [0, 2, 2], [1, 2, 3], [2, 3, 4]]
. The secret starts with person 0
and let's say firstPerson
is 1
, so both persons 0
and 1
know the secret at time 0
.
Step by step walkthrough:
-
Initialize the
vis
array to[True, True, False, False]
since persons0
and1
know the secret initially, and others don't. -
Sort the meetings by meeting times:
[[0, 1, 1], [0, 2, 2], [1, 2, 3], [2, 3, 4]]
(In our example, they are already sorted). -
We have the
while-loop
to process blocks of meetings based on unique times. We start with the first block at time1
. -
At time
1
, there is one meeting[0, 1, 1]
. We identify that both persons0
and1
are in meetings, and since they both knew the secret before, there is no new secret sharing occurring in this block. -
Move to the next block at time
2
, we see one meeting[0, 2, 2]
. We identify that person0
attends this meeting with person2
. Since person0
knows the secret, we share it with person2
, and now ourvis
array becomes[True, True, True, False]
. -
At time
3
, there is a meeting[1, 2, 3]
between persons1
and2
. Both of them already know the secret, so there is no change in thevis
array. -
Finally, at time
4
, there is a meeting[2, 3, 4]
where person2
shares the secret with person3
. So thevis
array updates to[True, True, True, True]
. -
The
while-loop
has now processed all meetings, and we collect the indices of thevis
array which areTrue
, which in this case returns[0, 1, 2, 3]
- indicating all persons know the secret.
Each person has had an opportunity to share the secret within their meetings according to the chronological order and BFS strategy, allowing us to accurately track the propagation of the secret.
Solution Implementation
1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5 def findAllPeople(self, n: int, meetings: List[List[int]], first_person: int) -> List[int]:
6 # Initialize visited list, setting 0 and first_person as True since they know the secret
7 visited = [False] * n
8 visited[0] = visited[first_person] = True
9
10 # Sort meetings by the time (third element in the meeting tuple)
11 meetings.sort(key=lambda x: x[2])
12
13 i, total_meetings = 0, len(meetings)
14
15 # Iterate through sorted meetings
16 while i < total_meetings:
17 # Find the range of meetings happening at the same time
18 j = i
19 while j + 1 < total_meetings and meetings[j + 1][2] == meetings[i][2]:
20 j += 1
21
22 # Set to store unique participants in meetings happening at the same time
23 participants = set()
24 # Graph representation (adjacency list) for people who meet at the same time
25 connections = defaultdict(list)
26
27 # Build the set of participants and the graph of connections
28 for person_a, person_b, _ in meetings[i : j + 1]:
29 connections[person_a].append(person_b)
30 connections[person_b].append(person_a)
31 participants.update([person_a, person_b])
32
33 # Queue to explore nodes (people) that know the secret
34 queue = deque([person for person in participants if visited[person]])
35
36 # BFS to propagate the secret among those meeting at the same time
37 while queue:
38 current_person = queue.popleft()
39 for neighbor in connections[current_person]:
40 if not visited[neighbor]:
41 visited[neighbor] = True
42 queue.append(neighbor)
43
44 # Increment index to the next time slot of meetings
45 i = j + 1
46
47 # Return a list of people who know the secret
48 return [person for person, knows_secret in enumerate(visited) if knows_secret]
49
1class Solution {
2 public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
3 // Create a visited array to keep track of people we've already found.
4 boolean[] visited = new boolean[n];
5 visited[0] = true; // Person 0 is always known.
6 visited[firstPerson] = true; // The firstPerson is initially known as well.
7
8 // Sort the array of meetings by the time they happen.
9 Arrays.sort(meetings, Comparator.comparingInt(a -> a[2]));
10
11 // Process meetings by batches of the same time.
12 for (int i = 0; i < meetings.length;) {
13 // Find the end index of the current batch.
14 int j = i;
15 while (j + 1 < meetings.length && meetings[j + 1][2] == meetings[i][2]) {
16 j++;
17 }
18
19 // Graph to keep connections at current time.
20 Map<Integer, List<Integer>> graph = new HashMap<>();
21 // Set to keep distinct people involved in the meetings of current time.
22 Set<Integer> peopleInMeetings = new HashSet<>();
23
24 for (int k = i; k <= j; k++) {
25 int personA = meetings[k][0];
26 int personB = meetings[k][1];
27
28 graph.computeIfAbsent(personA, key -> new ArrayList<>()).add(personB);
29 graph.computeIfAbsent(personB, key -> new ArrayList<>()).add(personA);
30 peopleInMeetings.add(personA);
31 peopleInMeetings.add(personB);
32 }
33
34 // Queue for Breadth-First Search (BFS).
35 Deque<Integer> queue = new ArrayDeque<>();
36
37 // Add people who are already known to the BFS queue.
38 for (int person : peopleInMeetings) {
39 if (visited[person]) {
40 queue.offer(person);
41 }
42 }
43
44 // Perform BFS to find all people that can be met at the current time.
45 while (!queue.isEmpty()) {
46 int currentPerson = queue.poll();
47 // Get neighbors or return empty list if no key exists in the map.
48 for (int neighbor : graph.getOrDefault(currentPerson, Collections.emptyList())) {
49 if (!visited[neighbor]) {
50 visited[neighbor] = true;
51 queue.offer(neighbor);
52 }
53 }
54 }
55
56 // Move to the start of the next batch of meetings.
57 i = j + 1;
58 }
59
60 // Prepare the result -- list of all known people.
61 List<Integer> result = new ArrayList<>();
62 for (int i = 0; i < n; i++) {
63 if (visited[i]) {
64 result.add(i);
65 }
66 }
67
68 return result; // Return the complete list of known people.
69 }
70}
71
1class Solution {
2public:
3 vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
4 // Flags to check if a person has discovered the secret
5 vector<bool> discovered(n, false);
6 // The first person and the '0'th person always know the secret
7 discovered[0] = true;
8 discovered[firstPerson] = true;
9
10 // Sort meetings based on the time
11 sort(meetings.begin(), meetings.end(), [](const auto& a, const auto& b) {
12 return a[2] < b[2];
13 });
14
15 // Iterate through the meetings
16 for (int i = 0, meetingsCount = meetings.size(); i < meetingsCount; ) {
17 int endIndex = i;
18 // Find all meetings that occur at the same time
19 while (endIndex + 1 < meetingsCount && meetings[endIndex + 1][2] == meetings[i][2]) {
20 ++endIndex;
21 }
22
23 // Graph to store connections during the same time
24 unordered_map<int, vector<int>> graph;
25 // Set to store all unique participants in the current time slot
26 unordered_set<int> participants;
27
28 // Build the graph for current time
29 for (int k = i; k <= endIndex; ++k) {
30 int personA = meetings[k][0], personB = meetings[k][1];
31 graph[personA].push_back(personB);
32 graph[personB].push_back(personA);
33 participants.insert(personA);
34 participants.insert(personB);
35 }
36
37 // Queue for BFS to discover all people who learn the secret
38 queue<int> queuePeople;
39
40 // Add discovered people to the queue as starting points
41 for (int person : participants) {
42 if (discovered[person]) {
43 queuePeople.push(person);
44 }
45 }
46
47 // BFS to spread the secret among people
48 while (!queuePeople.empty()) {
49 int currentPerson = queuePeople.front();
50 queuePeople.pop();
51
52 for (int neighbour : graph[currentPerson]) {
53 if (!discovered[neighbour]) {
54 discovered[neighbour] = true;
55 queuePeople.push(neighbour);
56 }
57 }
58 }
59
60 // Move to the next time slot
61 i = endIndex + 1;
62 }
63
64 // Collect all people who know the secret
65 vector<int> result;
66 for (int i = 0; i < n; ++i) {
67 if (discovered[i]) {
68 result.push_back(i);
69 }
70 }
71 return result;
72 }
73};
74
1function findAllPeople(n: number, meetings: number[][], firstPerson: number): number[] {
2 // Initialize a parent array to represent connections between people.
3 let parentArray: Array<number> = Array.from({ length: n + 1 }, (_, index) => index);
4 parentArray[firstPerson] = 0; // Connect the first person directly to person 0.
5
6 // Helper function to find the ultimate parent of a person.
7 function findParent(personIndex: number): number {
8 if (parentArray[personIndex] !== personIndex) {
9 parentArray[personIndex] = findParent(parentArray[personIndex]);
10 }
11 return parentArray[personIndex];
12 }
13
14 // A map to store lists of meetings by the time they occur.
15 let meetingTimesMap = new Map<number, Array<Array<number>>>();
16 for (let meeting of meetings) {
17 const time = meeting[2];
18 let timeMeetings: Array<Array<number>> = meetingTimesMap.get(time) || [];
19 timeMeetings.push(meeting);
20 meetingTimesMap.set(time, timeMeetings);
21 }
22
23 // Sort the times to process meetings in chronological order.
24 const sortedTimes = [...meetingTimesMap.keys()].sort((a, b) => a - b);
25
26 for (let time of sortedTimes) {
27 // First round to connect all people who meet at this time.
28 for (let meeting of meetingTimesMap.get(time)) {
29 let [personA, personB] = meeting;
30 let parentA = findParent(personA);
31 let parentB = findParent(personB);
32 if (parentArray[parentA] === 0 || parentArray[parentB] === 0) {
33 parentArray[parentA] = 0;
34 parentArray[parentB] = 0;
35 }
36 parentArray[findParent(personA)] = parentArray[findParent(personB)];
37 }
38
39 // Second round to reset meeting participant's parent if they shouldn't be connected.
40 for (let meeting of meetingTimesMap.get(time)) {
41 let [personA, personB] = meeting;
42 if (parentArray[findParent(personA)] !== 0 && parentArray[findParent(personB)] !== 0) {
43 parentArray[personA] = personA;
44 parentArray[personB] = personB;
45 }
46 }
47 }
48
49 // Collect all people who are still connected to person 0.
50 let peopleConnectedToZero: Array<number> = [];
51 for (let i = 0; i < n; i++) {
52 if (parentArray[findParent(i)] === 0) {
53 peopleConnectedToZero.push(i);
54 }
55 }
56
57 // Return the list of people that remain connected to person 0.
58 return peopleConnectedToZero;
59}
60
Time and Space Complexity
Time Complexity
The overall time complexity of the given code is O(m log m + m + n)
, where m
is the number of meetings and n
is the number of people.
Explanation:
meetings.sort(key=lambda x: x[2])
: This sort operation has a time complexity ofO(m log m)
because it sorts themeetings
array based on the time (third element in each sub-array).- The while loop: The outer while loop (
while i < m:
) iterates through all meetings, which isO(m)
. The inner while loop (while j + 1 < m and meetings[j + 1][2] == meetings[i][2]:
) increasesj
until the next meeting's time is different from the current one. While it seems to suggest anotherO(m)
complexity, these loops together effectively process each meeting exactly once, so they contribute onlyO(m)
in total, notO(m^2)
. - The BFS loop (
while q:
): There could be up ton
people in the queue since every person can be added at least once to the queue. Since we ensure that each person is only visited once by using thevis
array, the BFS iteration also contributesO(n)
complexity.
Therefore, when combined, the dominant term is the sorting step, m log m
, the total time complexity is O(m log m + m + n)
.
Space Complexity
The space complexity of the code is O(m + n)
.
Explanation:
vis = [False] * n
: This creates a list ofn
boolean values to mark the visited person which takesO(n)
space.s = set()
andg = defaultdict(list)
: In the worst case, the sets
and the adjacency listg
can store all unique people from the current batch of meetings processed. This requiresO(m)
space because we need to account for each edge in the adjacency list at least once, and there might be up tom
edges.q = deque([u for u in s if vis[u]])
: The queueq
can also store up ton
people in the worst case if everyone meets at the same time.
When combined, the terms involving n
and m
give us a total space complexity of O(m + n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.