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.
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
0andfirstPersonknow 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 (
visarray). - 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.
Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
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
visarray, which stands for "visited," is used to keep track of the people who know the secret. It is initialized withFalsevalues for each person and set toTruefor person0andfirstPerson, who know the secret initially. -
The
meetingsare 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 variablesiandjhelp identify the start and end index of meetings happening at the same time. -
A set
sis used to identify unique people participating in meetings at the current timet, while adefaultdictof lists, namedg, is formed to create an adjacency list representing connections (meetings) between people. -
Once the subgraph of meetings for time
tis 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 adequeto efficiently handle the BFS queue operations. -
The BFS proceeds by popping a person
ufrom the left of the queue and iterating over all the peoplevthey have meetings with at the current timet. If personvhas 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
viswho isTruenow knows the secret. -
The outer while-loop continues to the next block of meetings by updating
itoj + 1, and the process repeats until all meetings are processed. -
Finally, a list comprehension is used to collect all indices
iof thevisarray 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.
Which data structure is used to implement priority queue?
Example 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
visarray to[True, True, False, False]since persons0and1know 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-loopto 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 persons0and1are 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 person0attends this meeting with person2. Since person0knows the secret, we share it with person2, and now ourvisarray becomes[True, True, True, False]. -
At time
3, there is a meeting[1, 2, 3]between persons1and2. Both of them already know the secret, so there is no change in thevisarray. -
Finally, at time
4, there is a meeting[2, 3, 4]where person2shares the secret with person3. So thevisarray updates to[True, True, True, True]. -
The
while-loophas now processed all meetings, and we collect the indices of thevisarray 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]
491class 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}
711class 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};
741function 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}
60Which two pointer techniques do you use to check if a string is a palindrome?
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 themeetingsarray 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]:) increasesjuntil 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 tonpeople 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 thevisarray, 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 ofnboolean values to mark the visited person which takesO(n)space.s = set()andg = defaultdict(list): In the worst case, the setsand the adjacency listgcan 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 tomedges.q = deque([u for u in s if vis[u]]): The queueqcan also store up tonpeople 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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
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 Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.