Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Meetings at the same time can spread the secret through an entire connected group instantly. Connections from an earlier time must not transmit a secret learned later, so non-secret meeting groups are temporary, while membership in the secret-knowing group persists.

Approach

Initialize union-find with person zero connected to firstPerson. Sort meetings and process equal-time batches. First union every meeting pair in the batch, allowing simultaneous chains. Then reset the parents of participants whose components are not connected to person zero, removing connections that conveyed no secret. Keep the secret-connected components intact. After all batches, return every person connected to zero. Unioning the whole batch before resetting is essential for same-time propagation.

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        def find(x):
            if par[x] != x: par[x] = find(par[x])
            return par[x]
        
        def union(a, b):
            pa = find(a)
            pb = find(b)
            par[pb] = pa
        
        par = [i for i in range(n)]
        union(0, firstPerson)

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

        for x, y, t in meetings:
            mm[t].append((x, y))
        
        for t in mm:
            for x, y in mm[t]:
                union(x, y)
            
            for x, y in mm[t]:
                if find(x) != find(0):
                    par[x] = x
                    par[y] = y
        
        return [i for i in range(n) if find(i) == find(0)]

Complexity analysis

Let n be the people count and m = meetings.length. Sorting and path-compressed union-find without rank take O(m log(m + 1) + (n + m) log n) time. Auxiliary space is O(n + m), including grouping/sorting storage and parents. JavaScript find is iterative. Python find is recursive and can encounter an O(n)-deep parent chain before compression, so legal large inputs can exceed an unadjusted Python recursion limit.