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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find All People With Secret

Difficulty: Hard

Problem Description

Given an integer n indicating there are n people numbered from 0 to n - 1, and a 2D integer array meetings where meetings[i] = [xi, yi, timei] indicates that person xi and person yi have a meeting at timei. You are also given an integer firstPerson. Person 0 has a secret and shares it with firstPerson at time 0. The secret is shared during meetings instantaneously. Return a list of all the people that have the secret after all the meetings have taken place.

Key Insights

  • The secret-sharing process occurs instantaneously during meetings.
  • Meetings can occur at the same time, allowing for multiple exchanges of information.
  • A graph-like approach can be utilized where each person is a node and each meeting is an edge connecting two nodes.
  • A breadth-first search (BFS) or depth-first search (DFS) can be employed to propagate the secret through connected nodes.

Space and Time Complexity

Time Complexity: O(M log M + M + N) where M is the number of meetings and N is the number of people. The log M accounts for sorting the meetings. Space Complexity: O(N + M) for storing the adjacency list and visited nodes.

Solution

To solve this problem, we will:

  1. Sort the meetings based on time to process them in chronological order.
  2. Use a set to keep track of people who know the secret.
  3. Iterate through the sorted meetings and use a BFS or DFS to propagate the secret among attendees of each meeting at the same time.
  4. Return the final list of people who know the secret.

Code Solutions

def findAllPeople(n, meetings, firstPerson):
    from collections import defaultdict, deque
    
    # Step 1: Sort meetings by time
    meetings.sort(key=lambda x: x[2])
    
    # Step 2: Initialize known secret holders
    known = {0, firstPerson}
    
    # Adjacency list to hold meetings
    graph = defaultdict(list)
    time = 0
    
    for x, y, t in meetings:
        if t != time:
            # Step 3: Process previous meetings
            if known:
                temp = set(known)
                for person in known:
                    for neighbor in graph[person]:
                        temp.add(neighbor)
                known = temp
            
            # Update time
            time = t

        # Add meeting to graph
        graph[x].append(y)
        graph[y].append(x)
    
    # Process the last meetings
    if known:
        temp = set(known)
        for person in known:
            for neighbor in graph[person]:
                temp.add(neighbor)
        known = temp

    return list(known)
← Back to All Questions