Find All People With Secret

Hard

Asked by:

52 views

Topics:

ArraysGreedy AlgorithmsGraphs

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] = [x_i, y_i, time_i] indicates that person x_i and person y_i have a meeting at time_i. 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 x_i has the secret at time_i, then they will share the secret with person y_i, 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 <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= x_i, y_i<= n - 1
x_i != y_i
1 <= time_i <= 10⁵
1 <= firstPerson <= n - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of people (`n`) and the number of meetings (`meetings.length`)?
What are the possible ranges for the time values in the `meetings` array? Can a meeting occur at time 0?
Is it possible for a person to meet with themselves, or for duplicate meetings to exist in the `meetings` array?
If no one initially knows the secret besides person 0 and the first person, should I return an empty list or a list containing only those initial individuals if no further spread occurs?
In the case of multiple valid solutions (multiple people know the secret), is the order of people in the returned list significant?

Brute Force Solution

Approach

We need to figure out who eventually knows a secret, starting from a specific person and a series of meetings. The brute force approach is like simulating every possible chain of information spreading until we can't find anyone new who learns the secret.

Here's how the algorithm would work step-by-step:

Initially, we know the first person and the secret holder know the secret.
Go through each meeting and check: if anyone in the meeting already knows the secret, then tell everyone else in that meeting the secret.
Repeat the previous step multiple times. Each time you go through the meetings, you're essentially seeing if the secret can spread further from those who newly learned it in the previous round.
Keep repeating this process of going through all the meetings, updating who knows the secret, until no one new learns the secret after going through all meetings once.
Finally, list all the people who know the secret.

Code Implementation

def find_all_people_with_secret(number_of_people, meetings, first_person):
    people_with_secret = {first_person, 0}

    secret_spread = True
    while secret_spread:
        secret_spread = False
        # Iterate meetings to see if secret can spread

        for meeting_time, (person_one, person_two) in enumerate(meetings):
            if person_one in people_with_secret or person_two in people_with_secret:

                # If anyone in meeting knows secret, share it
                if person_one not in people_with_secret:
                    people_with_secret.add(person_one)
                    secret_spread = True

                if person_two not in people_with_secret:
                    people_with_secret.add(person_two)
                    secret_spread = True

    return sorted(list(people_with_secret))

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through the meetings (m) in a loop until no new person learns the secret. In the worst-case scenario, each person (n) might learn the secret one by one. Therefore, the outer loop could potentially run 'n' times, representing the times the secret can further spread. Inside this loop, we iterate through all the 'm' meetings to check if the secret can be spread in the particular round. Hence, the overall time complexity is O(m*n), where 'm' is the number of meetings and 'n' is the number of people. This is because in the worst case we iterate through all meetings a number of times proportional to the number of people.

Space Complexity

O(N) – The solution uses a data structure (e.g., a set or boolean array) to keep track of all the people who know the secret. This data structure has a size proportional to the number of people, where N represents the total number of people. In the worst case, everyone might eventually learn the secret, requiring space to store information about each person. Thus, the auxiliary space is O(N).

Optimal Solution

Approach

The problem involves finding everyone who eventually learns a secret starting from an initial group. The efficient approach involves tracking who knows the secret over time as meetings happen, using a method to merge groups of people who share the secret.

Here's how the algorithm would work step-by-step:

Start with the initial group of people who know the secret.
Go through the meetings in order of time they occur. This is important to follow the flow of information.
For each meeting, check if anyone involved already knows the secret.
If someone in the meeting knows the secret, then everyone in that meeting learns the secret.
Keep track of all the people who have learned the secret.
After going through all the meetings, report everyone who knows the secret.

Code Implementation

def find_all_people_with_secret(number_of_people, meetings, first_person):
    knows_secret = [False] * number_of_people
    knows_secret[0] = True
    knows_secret[first_person] = True

    meetings.sort(key=lambda x: x[2])

    for time in sorted(list(set(meeting[2] for meeting in meetings))):
        current_meeting_people = set()
        relevant_meetings = []

        for person1, person2, meeting_time in meetings:
            if meeting_time == time:
                current_meeting_people.add(person1)
                current_meeting_people.add(person2)
                relevant_meetings.append((person1, person2))

        secret_present = False
        for person in current_meeting_people:
            if knows_secret[person]:
                secret_present = True
                break

        # If no one in the meeting knows the secret, skip to next meeting
        if not secret_present:
            continue

        # If someone in the meeting knows the secret, everyone learns it
        for person1, person2 in relevant_meetings:
            knows_secret[person1] = True
            knows_secret[person2] = True

    people_with_secret = [i for i, knows in enumerate(knows_secret) if knows]
    return people_with_secret

Big(O) Analysis

Time Complexity

O(m log m + m * n) – The algorithm first sorts the meetings based on time, which takes O(m log m) time where m is the number of meetings. Then, for each meeting (m), it iterates through the people involved to check if anyone knows the secret. In the worst case, for each of the m meetings, it might need to check up to n people (where n is the number of people) to update the knowledge about the secret. Therefore, the total time complexity is dominated by the sorting and the meeting processing, resulting in O(m log m + m * n), which can be simplified to O(m * n) if m dominates the log m component.

Space Complexity

O(N) – The algorithm maintains a set or list to keep track of all people who have learned the secret. In the worst-case scenario, every person could learn the secret, resulting in the storage of N people's IDs, where N is the total number of people. No other significant data structures are used that depend on the size of the input. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty meetings array	If meetings is empty, only the first person has the secret; return [firstPerson].
Only one person in meetings	The solution should still correctly identify the spread of the secret from the initial person.
All meetings involve the first person	Ensure efficient spreading of the secret among all connected people.
Disjoint groups; some groups do not have the secret	Only the groups connected to the initial person should have the secret.
Very large number of people and meetings (scalability)	Use efficient data structures (e.g., disjoint set union with path compression) to avoid time limit exceeded errors.
Meetings with the same people at different times	Process meetings in chronological order to ensure the secret spreads correctly based on the earliest meeting time.
Cycles in the meeting graph	The algorithm should handle cycles correctly and prevent infinite loops or incorrect secret propagation.
Integer overflow in meeting time	The algorithm should use appropriate data types (e.g., long) for meeting times to avoid overflow issues.

Empty meetings array

How to Handle:

If meetings is empty, only the first person has the secret; return [firstPerson].

Only one person in meetings

How to Handle:

The solution should still correctly identify the spread of the secret from the initial person.

All meetings involve the first person

How to Handle:

Ensure efficient spreading of the secret among all connected people.

Disjoint groups; some groups do not have the secret

How to Handle:

Only the groups connected to the initial person should have the secret.

Very large number of people and meetings (scalability)

How to Handle:

Use efficient data structures (e.g., disjoint set union with path compression) to avoid time limit exceeded errors.

Meetings with the same people at different times

How to Handle:

Process meetings in chronological order to ensure the secret spreads correctly based on the earliest meeting time.

Cycles in the meeting graph

How to Handle:

The algorithm should handle cycles correctly and prevent infinite loops or incorrect secret propagation.

Integer overflow in meeting time

How to Handle:

The algorithm should use appropriate data types (e.g., long) for meeting times to avoid overflow issues.