2092. Find All People With Secret

HardDepth-First SearchBreadth-First SearchUnion FindGraphSorting

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 and firstPerson 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 with False values for each person and set to True for person 0 and firstPerson, 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 variables i and j 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 time t, while a defaultdict of lists, named g, 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 a deque 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 people v they have meetings with at the current time t. If person v 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 is True now knows the secret.
The outer while-loop continues to the next block of meetings by updating i to j + 1, and the process repeats until all meetings are processed.
Finally, a list comprehension is used to collect all indices i of the vis array that are True, 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 Evaluator

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 vis array to [True, True, False, False] since persons 0 and 1 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 time 1.
At time 1, there is one meeting [0, 1, 1]. We identify that both persons 0 and 1 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 person 0 attends this meeting with person 2. Since person 0 knows the secret, we share it with person 2, and now our vis array becomes [True, True, True, False].
At time 3, there is a meeting [1, 2, 3] between persons 1 and 2. Both of them already know the secret, so there is no change in the vis array.
Finally, at time 4, there is a meeting [2, 3, 4] where person 2 shares the secret with person 3. So the vis array updates to [True, True, True, True].
The while-loop has now processed all meetings, and we collect the indices of the vis array which are True, 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 of O(m log m) because it sorts the meetings 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 is O(m). The inner while loop (while j + 1 < m and meetings[j + 1][2] == meetings[i][2]:) increases j until the next meeting's time is different from the current one. While it seems to suggest another O(m) complexity, these loops together effectively process each meeting exactly once, so they contribute only O(m) in total, not O(m^2).
The BFS loop (while q:): There could be up to n 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 the vis array, the BFS iteration also contributes O(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).