LeetCode 2092 - Find All People With Secret

The problem describes a network of people who meet at different times. Whenever a person who already knows a secret participates in a meeting, they immediately share the secret with the other participant. The key detail is that sharing is instantaneous within the same timestamp.

leetcodeharddepth-first-searchbreadth-first-searchunion-findgraph-theorysorting

LeetCode Problem 2092

Difficulty: 🔴 Hard
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Sorting

Solution

Problem Understanding

The problem describes a network of people who meet at different times. Whenever a person who already knows a secret participates in a meeting, they immediately share the secret with the other participant. The key detail is that sharing is instantaneous within the same timestamp. This means if someone learns the secret during a meeting at time t, they can immediately pass it along in another meeting that also happens at time t.

We are given:

  • n, the total number of people labeled from 0 to n - 1
  • meetings, where each entry is [x, y, time]
  • firstPerson, the person who learns the secret directly from person 0 at time 0

Initially:

  • Person 0 knows the secret
  • Person firstPerson also knows the secret because person 0 tells them at time 0

We must determine every person who eventually learns the secret after all meetings occur.

The major challenge comes from meetings that occur at the same time. Consider this sequence at the same timestamp:

1 meets 2
2 meets 3
3 meets 4

If person 1 initially knows the secret, then during that same timestamp:

  • 1 tells 2
  • 2 immediately tells 3
  • 3 immediately tells 4

So all four people end up knowing the secret during the same time block.

The constraints are large:

  • Up to 10^5 people
  • Up to 10^5 meetings

This immediately rules out naive repeated simulation approaches that repeatedly propagate secrets across all meetings.

Several edge cases are important:

  • Multiple meetings occurring at the exact same time
  • Disconnected meeting groups
  • Cycles inside the same timestamp
  • People attending multiple simultaneous meetings
  • Meetings where neither participant knows the secret
  • Chains of propagation entirely inside one timestamp

The problem guarantees valid meeting data and distinct participants in each meeting.

Approaches

Brute Force Approach

A brute force solution would repeatedly scan all meetings in chronological order and keep propagating the secret until no more changes occur.

For every timestamp:

  1. Iterate through all meetings at that time.
  2. If either participant knows the secret, give it to the other.
  3. Because propagation inside the same timestamp is instantaneous, repeat the scan until no new person learns the secret.

This approach is correct because eventually all reachable people within a timestamp receive the secret.

However, it is too slow. In the worst case, each timestamp could require repeated rescanning of many meetings. With up to 10^5 meetings, repeated propagation becomes expensive and can degrade toward quadratic behavior.

Key Insight

The important observation is that meetings occurring at the same time form temporary communication graphs.

Within one timestamp:

  • Every connected component behaves as a fully propagating network
  • If any person in that connected component already knows the secret, then the entire component learns it

This transforms the problem into:

  1. Process meetings grouped by time
  2. Build connected components for that timestamp
  3. Check whether each component contains someone who already knows the secret
  4. If yes, everyone in that component learns the secret

A Union-Find data structure is ideal for this because:

  • It efficiently groups connected participants
  • It supports near constant time merging and lookup
  • We can process each timestamp independently

The subtle part is that connections only exist temporarily during one timestamp. Therefore, after processing a time group, we must reset components that did not gain the secret.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m²) O(n) Repeatedly rescans meetings within timestamps
Optimal O(m log m) O(n) Uses sorting and Union-Find grouped by time

Where m = len(meetings).

Algorithm Walkthrough

Step 1: Sort Meetings by Time

We first sort all meetings by their timestamp.

This ensures meetings are processed in chronological order, because secrets cannot travel backward in time.

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

Step 2: Initialize Union-Find

We create a Union-Find structure for all n people.

Initially:

  • Person 0 knows the secret
  • Person firstPerson also knows the secret

We immediately connect them in Union-Find.

This means anyone connected to person 0 is considered to know the secret.

Step 3: Process Meetings Time Block by Time Block

Meetings with the same timestamp must be processed together because propagation inside the same time is instantaneous.

For each timestamp:

  1. Collect all meetings occurring at that time
  2. Union all meeting participants
  3. Record all people involved during this timestamp

Step 4: Determine Which Components Gain the Secret

After all unions for the current timestamp are complete:

  • Any participant connected to person 0 knows the secret
  • Entire connected components gain the secret simultaneously

Step 5: Reset Components Without the Secret

This is the most important step.

Some people may become connected during this timestamp but still never reach person 0.

Those temporary connections must not persist into future timestamps.

For every participant involved in the current timestamp:

  • If they are not connected to person 0
  • Reset their parent to themselves

This removes invalid temporary connections.

Step 6: Continue Until All Meetings Are Processed

Repeat the same process for every timestamp.

Step 7: Collect Final Answer

At the end:

  • Every person connected to person 0 knows the secret

Return all such people.

Why it works

At each timestamp, Union-Find correctly groups all people who can communicate instantaneously during that time. If any member of a connected component already knows the secret, the secret propagates throughout the entire component. Resetting components that never connect to person 0 ensures temporary communication links do not incorrectly persist into future timestamps. Therefore, after all timestamps are processed, exactly the people reachable through valid chronological propagation remain connected to person 0.

Python Solution

from typing import List

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return

        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def reset(self, x: int) -> None:
        self.parent[x] = x

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        meetings.sort(key=lambda x: x[2])

        uf = UnionFind(n)
        uf.union(0, firstPerson)

        i = 0
        total_meetings = len(meetings)

        while i < total_meetings:
            current_time = meetings[i][2]
            participants = set()

            j = i

            while j < total_meetings and meetings[j][2] == current_time:
                x, y, _ = meetings[j]

                uf.union(x, y)

                participants.add(x)
                participants.add(y)

                j += 1

            for person in participants:
                if not uf.connected(person, 0):
                    uf.reset(person)

            i = j

        result = []

        for person in range(n):
            if uf.connected(person, 0):
                result.append(person)

        return result

The implementation begins by sorting meetings chronologically. This guarantees that information only flows forward in time.

The UnionFind class manages connected components efficiently. Path compression in find() and union by rank in union() keep operations nearly constant time.

The algorithm unions all participants within the same timestamp before checking connectivity. This is essential because secret sharing inside a timestamp is instantaneous and may require multi-step propagation.

The participants set records everyone involved during the current timestamp. After all unions are complete, we inspect each participant:

  • If they are connected to person 0, they permanently keep the secret
  • Otherwise, their temporary timestamp connections are removed using reset()

Finally, everyone connected to person 0 is returned.

Go Solution

package main

import (
	"sort"
)

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	return &UnionFind{
		parent: parent,
		rank:   rank,
	}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x int, y int) {
	rootX := uf.Find(x)
	rootY := uf.Find(y)

	if rootX == rootY {
		return
	}

	if uf.rank[rootX] < uf.rank[rootY] {
		uf.parent[rootX] = rootY
	} else if uf.rank[rootX] > uf.rank[rootY] {
		uf.parent[rootY] = rootX
	} else {
		uf.parent[rootY] = rootX
		uf.rank[rootX]++
	}
}

func (uf *UnionFind) Connected(x int, y int) bool {
	return uf.Find(x) == uf.Find(y)
}

func (uf *UnionFind) Reset(x int) {
	uf.parent[x] = x
}

func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
	sort.Slice(meetings, func(i, j int) bool {
		return meetings[i][2] < meetings[j][2]
	})

	uf := NewUnionFind(n)
	uf.Union(0, firstPerson)

	i := 0
	totalMeetings := len(meetings)

	for i < totalMeetings {
		currentTime := meetings[i][2]
		participantsMap := make(map[int]bool)

		j := i

		for j < totalMeetings && meetings[j][2] == currentTime {
			x := meetings[j][0]
			y := meetings[j][1]

			uf.Union(x, y)

			participantsMap[x] = true
			participantsMap[y] = true

			j++
		}

		for person := range participantsMap {
			if !uf.Connected(person, 0) {
				uf.Reset(person)
			}
		}

		i = j
	}

	result := []int{}

	for person := 0; person < n; person++ {
		if uf.Connected(person, 0) {
			result = append(result, person)
		}
	}

	return result
}

The Go implementation follows the same logic as the Python solution. Go does not provide built in sets, so a map[int]bool is used to track timestamp participants. Slices are used for the parent and rank arrays. Integer overflow is not a concern because all values remain well within Go's integer limits.

Worked Examples

Example 1

n = 6
meetings = [[1,2,5],[2,3,8],[1,5,10]]
firstPerson = 1

Initially:

Secret holders = {0, 1}

Time = 5

Meeting:

1 meets 2

Union:

1 <-> 2

Since 1 already knows the secret:

Secret holders = {0,1,2}
Person Connected to 0
1 Yes
2 Yes

Time = 8

Meeting:

2 meets 3

Union:

2 <-> 3

Since 2 knows the secret:

Secret holders = {0,1,2,3}
Person Connected to 0
2 Yes
3 Yes

Time = 10

Meeting:

1 meets 5

Union:

1 <-> 5

Since 1 knows the secret:

Secret holders = {0,1,2,3,5}

Final answer:

[0,1,2,3,5]

Example 2

n = 4
meetings = [[3,1,3],[1,2,2],[0,3,3]]
firstPerson = 3

Initially:

Secret holders = {0,3}

Time = 2

Meeting:

1 meets 2

Neither knows the secret.

Temporary union occurs, but afterward neither is connected to 0.

So both are reset.

Secret holders = {0,3}

Time = 3

Meetings:

3 meets 1
0 meets 3

Connected component:

0 - 3 - 1

Since 0 and 3 know the secret:

1 also learns it

Final answer:

[0,1,3]

Example 3

n = 5
meetings = [[3,4,2],[1,2,1],[2,3,1]]
firstPerson = 1

Initially:

Secret holders = {0,1}

Time = 1

Meetings:

1 meets 2
2 meets 3

Connected component:

1 - 2 - 3

Since 1 knows the secret:

2 and 3 learn it immediately

Secret holders become:

{0,1,2,3}

Time = 2

Meeting:

3 meets 4

Since 3 knows the secret:

4 learns it

Final answer:

[0,1,2,3,4]

Complexity Analysis

Measure Complexity Explanation
Time O(m log m) Sorting meetings dominates the complexity
Space O(n) Union-Find arrays and participant tracking

Here, m is the number of meetings.

Union-Find operations are nearly constant time because of path compression and union by rank. Although each meeting performs union and find operations, the amortized complexity is effectively linear after sorting.

Test Cases

from typing import List

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        parent = list(range(n))
        rank = [0] * n

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            rx = find(x)
            ry = find(y)

            if rx == ry:
                return

            if rank[rx] < rank[ry]:
                parent[rx] = ry
            elif rank[rx] > rank[ry]:
                parent[ry] = rx
            else:
                parent[ry] = rx
                rank[rx] += 1

        def connected(x, y):
            return find(x) == find(y)

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

        union(0, firstPerson)

        i = 0

        while i < len(meetings):
            t = meetings[i][2]
            participants = set()

            j = i

            while j < len(meetings) and meetings[j][2] == t:
                x, y, _ = meetings[j]

                union(x, y)

                participants.add(x)
                participants.add(y)

                j += 1

            for p in participants:
                if not connected(p, 0):
                    parent[p] = p

            i = j

        return [i for i in range(n) if connected(i, 0)]

sol = Solution()

assert sorted(sol.findAllPeople(
    6,
    [[1,2,5],[2,3,8],[1,5,10]],
    1
)) == [0,1,2,3,5]  # Basic propagation chain

assert sorted(sol.findAllPeople(
    4,
    [[3,1,3],[1,2,2],[0,3,3]],
    3
)) == [0,1,3]  # Temporary disconnected component

assert sorted(sol.findAllPeople(
    5,
    [[3,4,2],[1,2,1],[2,3,1]],
    1
)) == [0,1,2,3,4]  # Instant propagation in same timestamp

assert sorted(sol.findAllPeople(
    2,
    [],
    1
)) == [0,1]  # No meetings

assert sorted(sol.findAllPeople(
    5,
    [[1,2,1],[2,3,1],[3,4,1]],
    1
)) == [0,1,2,3,4]  # Entire chain in one timestamp

assert sorted(sol.findAllPeople(
    5,
    [[2,3,1],[3,4,1]],
    1
)) == [0,1]  # No propagation possible

assert sorted(sol.findAllPeople(
    6,
    [[1,2,2],[2,3,2],[4,5,2]],
    1
)) == [0,1,2,3]  # One component learns secret, another does not

assert sorted(sol.findAllPeople(
    7,
    [[1,2,5],[2,3,5],[3,4,5],[4,5,5],[5,6,5]],
    1
)) == [0,1,2,3,4,5,6]  # Large same-time propagation

assert sorted(sol.findAllPeople(
    5,
    [[1,2,1],[2,3,2],[3,4,3]],
    2
)) == [0,1,2,3,4]  # Sequential propagation over time

Test Summary

Test Why
Example 1 Verifies standard chronological propagation
Example 2 Verifies temporary components are reset
Example 3 Verifies same timestamp chaining
No meetings Verifies initialization correctness
Single timestamp chain Verifies instantaneous propagation
Disconnected meetings Verifies no accidental spread
Multiple components Verifies selective propagation
Large simultaneous chain Stress tests timestamp grouping
Sequential propagation Verifies multi-time spreading

Edge Cases

Multiple Meetings at the Same Time

A major source of bugs is failing to process all meetings of the same timestamp together. If processed one by one independently, propagation chains inside the same timestamp would break incorrectly.

For example:

1 meets 2 at time 5
2 meets 3 at time 5

If person 1 knows the secret, person 3 should also learn it immediately. The implementation handles this by unioning every meeting for a timestamp before checking connectivity.

Temporary Connections That Should Not Persist

Another subtle issue is allowing disconnected groups to remain unioned across timestamps.

For example:

1 meets 2 at time 1
2 meets 3 at time 2

If nobody initially knows the secret, the connection between 1 and 2 from time 1 should not remain active at time 2.

The reset step ensures temporary components disappear unless they connect to person 0.

Chains Inside One Timestamp

Propagation can occur through multiple intermediate people within the same timestamp.

For example:

1 meets 2
2 meets 3
3 meets 4

all at the same time.

A naive sequential update might fail to fully propagate the secret. Because the algorithm builds the entire connected component first, everyone reachable within the timestamp correctly receives the secret.