Find All People With Secret — Hard Problem & Solution

There are n people labelled 0 … n - 1. Person 0 holds a secret and shares it with firstPerson at time 0.

Difficulty: Hard
Topics: Sorting, Breadth-First Search, Depth-First Search, Graph, Union Find
Asked at: Amazon, Google, Swiggy
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n people labelled 0 … n - 1. Person 0 holds a secret and shares it with firstPerson at time 0.

meetings[i] = [x, y, time] says persons x and y meet at that time. People who meet share the secret immediately, so a person who learns it during a meeting can pass it on in any other meeting happening at the same time. Meetings may happen at the same time, and a person may attend several of them.

Return everyone who ends up knowing the secret, in increasing 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: Person 4 never meets anyone who knows.

Example 2

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation: Person 2's meeting with 1 happens *before* 1 learns anything.

Example 3

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]

Constraints

2 <= n <= 10^5
1 <= meetings.length <= 10^5
meetings[i].length == 3
0 <= x, y <= n - 1
x != y
1 <= time <= 10^5
1 <= firstPerson <= n - 1
The answer is returned in increasing order.

How to solve Find All People With Secret

Sort the meetings by time and process each equal-time batch together. Within a batch, union every pair; afterwards, anyone in the batch not joined to person 0's component is reset to a singleton so a later meeting does not wrongly spread the secret through them.

Approach

Union person 0 with firstPerson.
Sort the meetings by time and walk them in equal-time runs.
Union both attendees of each meeting in the run.
For each person in the run, if their root is not person 0's root, reset their parent to themselves.
Finally collect every person sharing person 0's root.

Why it works

The reset is the whole problem: without it, two people who merely met earlier would stay connected, so a secret arriving at one of them later would appear to have reached the other backwards in time. Resetting only the batch's participants is safe because, by induction, every component is either person 0's or a singleton before the batch begins.

Complexity

Time — O(m log m + n)
Space — O(n)

Pitfalls

Processing meetings one at a time misses the secret hopping between simultaneous meetings.
Forgetting the reset lets the secret travel backwards in time.
The output must be sorted; walking the people in order gives that for free.

Reference solution

Python

from typing import List

def findAllPeople(n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def uni(a: int, b: int) -> None:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra

    uni(0, firstPerson)
    ordered = sorted(meetings, key=lambda m: m[2])
    i = 0
    while i < len(ordered):
        j = i
        while j < len(ordered) and ordered[j][2] == ordered[i][2]:
            j += 1
        people = []
        for k in range(i, j):
            people.append(ordered[k][0])
            people.append(ordered[k][1])
            uni(ordered[k][0], ordered[k][1])
        root = find(0)
        for p in people:
            if find(p) != root:
                parent[p] = p
        i = j
    root = find(0)
    return [p for p in range(n) if find(p) == root]

JavaScript

var findAllPeople = function(n, meetings, firstPerson) {
    var i, k;
    var parent = [];
    for (i = 0; i < n; i++) parent.push(i);
    var find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    var uni = function(a, b) {
        var ra = find(a), rb = find(b);
        if (ra !== rb) parent[rb] = ra;
    };
    uni(0, firstPerson);
    var sorted = meetings.slice();
    sorted.sort(function(a, b) { return a[2] - b[2]; });
    i = 0;
    while (i < sorted.length) {
        var j = i;
        while (j < sorted.length && sorted[j][2] === sorted[i][2]) j++;
        var people = [];
        for (k = i; k < j; k++) {
            people.push(sorted[k][0]);
            people.push(sorted[k][1]);
            uni(sorted[k][0], sorted[k][1]);
        }
        var root = find(0);
        for (k = 0; k < people.length; k++) {
            if (find(people[k]) !== root) parent[people[k]] = people[k];
        }
        i = j;
    }
    var out = [];
    var finalRoot = find(0);
    for (var p = 0; p < n; p++) if (find(p) === finalRoot) out.push(p);
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 sorting problems · the whole catalogue