We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All People With Secret

Number: 2213

Difficulty: Hard

Paid? No

Companies: Amazon, Adobe, Google

Problem Description

There are n people numbered from 0 to n-1. Person 0 initially knows a secret and immediately shares it with firstPerson at time 0. A list of meetings is provided where each meeting is represented as [x, y, time] indicating that person x and person y meet at the specified time. During a meeting, if any participant knows the secret by that time, they share it with the other person. Meetings occurring at the same time allow instantaneous sharing, meaning a person can both receive and then share the secret within the same time frame. The goal is to output the list of all people who know the secret after all meetings are processed.

Key Insights

  • Meetings must be processed in chronological order.
  • Multiple meetings at the same time can be grouped together, and the secret can spread within the whole connected component.
  • Using union-find (disjoint set union) to group people meeting at the same time helps efficiently determine connected components.
  • After processing a time group, any connected component that contains a person with the secret will have all its members learn the secret.
  • Reset the union-find structure for each new time group to isolate interactions.

Space and Time Complexity

Time Complexity: O(m log m + m α(n)) where m is the number of meetings and α(n) is the inverse Ackermann function (nearly constant time per union-find operation).
Space Complexity: O(n + m)

Solution

We start by sorting the meetings by time. For each set of meetings with the same time stamp, we initialize a temporary union-find structure limited to the people involved in that time slot. Within this group, we union the meeting pairs. Next, for each connected component, we check if any member already knows the secret. If so, we mark all members of that component as having the secret. After processing a time group, we clear the union-find connections and move to the next time group. Finally, we return the list of people who know the secret.

Code Solutions

# Python solution using union-find

class UnionFind:
    def __init__(self):
        # parent mapping for each node
        self.parent = {}

    def find(self, x):
        # path compression find
        if self.parent.setdefault(x, x) != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # union two nodes by root
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def findAllPeople(n, meetings, firstPerson):
    # Initially known secret holders: person 0 and firstPerson
    secret = [False] * n
    secret[0] = True
    secret[firstPerson] = True

    # Sort meetings by time
    meetings.sort(key=lambda x: x[2])
    i = 0
    m = len(meetings)

    # Process meetings group by same time
    while i < m:
        time = meetings[i][2]
        uf = UnionFind()
        # record all unique people in current group
        participants = set()
        # Process all meetings with the same time stamp
        while i < m and meetings[i][2] == time:
            x, y, _ = meetings[i]
            uf.union(x, y)
            participants.add(x)
            participants.add(y)
            i += 1

        # Mapping from group leader to all members in that group
        groupMembers = {}
        for person in participants:
            root = uf.find(person)
            if root not in groupMembers:
                groupMembers[root] = []
            groupMembers[root].append(person)

        # If any member in group has the secret, mark all as secret-holders
        for members in groupMembers.values():
            if any(secret[person] for person in members):
                for person in members:
                    secret[person] = True

    # Collect and return all people who know the secret
    return [i for i, hasSecret in enumerate(secret) if hasSecret]

# Example usage:
print(findAllPeople(6, [[1,2,5],[2,3,8],[1,5,10]], 1))
← Back to All Questions