Find All People With Secret

Hard · Graphs · Explanation and code example

Disjoint Set Union

How it works

We can model the secret-sharing as a union-find problem. People who meet at the same time are temporarily connected. If any person in a connected component knows the secret (i.e., is connected to person 0), everyone in that component learns it. The key insight is that after processing each time slot, we must reset people who did not get connected to person 0, since the secret only spreads within a time slot.

Steps

  1. Sort meetings by time.
  2. Initialize a DSU structure. Union person 0 and firstPerson.
  3. Process meetings in groups by time:
    • Union all pairs of people meeting at this time.
    • Track all people involved in meetings at this time.
    • After all unions for this time, reset any person not connected to person 0 (they do not know the secret yet).
  4. Return all people who are in the same component as person 0.

Complexity

  • Time complexity: O(m log m + (m * α(n)))
  • Space complexity:
    • O(n) extra space.
    • O(m) space depending on the sorting algorithm.

Where m is the number of meetings and n is the number of people.

Things to watch for

Ignoring the Time Ordering

Processing meetings without sorting by time first causes secrets to propagate incorrectly. The secret can only spread chronologically, so meetings must be grouped and handled in ascending time order.

Not Resetting DSU Nodes After Each Time Slot

In the Union-Find approach, failing to reset nodes that did not connect to person 0 allows stale union relationships to persist. After each time slot, any person not in the same component as person 0 must be reset to their own parent.

Using a Single Visited Set Across All Time Slots

Reusing the same visited set across different time slots prevents the secret from spreading correctly within each slot. Each time group requires a fresh visited set since a person might need to be visited again at a later time.

Missing Bidirectional Edge Construction

Only adding edges in one direction when building the adjacency list causes incomplete graph traversal. Both adj[u].append(v) and adj[v].append(u) are required since meetings are mutual.

Forgetting to Include firstPerson Initially

Initializing the secret holders with only person 0 and forgetting to add firstPerson causes incorrect results. The problem states that person 0 shares the secret with firstPerson at time 0.

Python code example

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] < self.Size[pv]:
            pu, pv = pv, pu
        self.Size[pu] += self.Size[pv]
        self.Parent[pv] = pu
        return True

    def reset(self, node):
        self.Parent[node] = node
        self.Size[node] = 1

class Solution:
    def findAllPeople(self, n: int, meetings: list[list[int]], firstPerson: int) -> list[int]:
        meetings.sort(key=lambda x: x[2])  # Sort by time
        dsu = DSU(n)
        dsu.union(0, firstPerson)

        for _, group in groupby(meetings, key=lambda x: x[2]):
            group_nodes = set()
            for u, v, _ in group:
                dsu.union(u, v)
                group_nodes.add(u)
                group_nodes.add(v)

            for node in group_nodes:
                if dsu.find(node) != dsu.find(0):
                    dsu.reset(node)

        return [i for i in range(n) if dsu.find(i) == dsu.find(0)]

C++ code example

class DSU {
public:
    vector<int> Parent, Size;

    DSU(int n) {
        Parent.resize(n + 1);
        Size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
        }
    }

    int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    void unionSets(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return;
        if (Size[pu] < Size[pv]) swap(pu, pv);
        Size[pu] += Size[pv];
        Parent[pv] = pu;
    }

    void reset(int node) {
        Parent[node] = node;
        Size[node] = 1;
    }
};

class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        sort(meetings.begin(), meetings.end(), [](auto &a, auto &b) {
            return a[2] < b[2];
        });
        DSU dsu(n);
        dsu.unionSets(0, firstPerson);

        for (int i = 0; i < meetings.size(); ) {
            int time = meetings[i][2];
            unordered_set<int> group;

            for (; i < meetings.size() && meetings[i][2] == time; i++) {
                int u = meetings[i][0], v = meetings[i][1];
                dsu.unionSets(u, v);
                group.insert(u);
                group.insert(v);
            }

            for (int node : group) {
                if (dsu.find(node) != dsu.find(0)) {
                    dsu.reset(node);
                }
            }
        }

        vector<int> result;
        for (int i = 0; i < n; i++) {
            if (dsu.find(i) == dsu.find(0)) result.push_back(i);
        }
        return result;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations