2092. Find All People With Secret

Source: Dev.to

Problem Description

You are given an integer n indicating there are n people numbered from 0 to n - 1.
You are also given a 0-indexed 2D integer array meetings where meetings[i] = [xᵢ, yᵢ, timeᵢ] indicates that person xᵢ and person yᵢ have a meeting at timeᵢ. A person may attend multiple meetings at the same time.

Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person xᵢ has the secret at timeᵢ, then they will share the secret with person yᵢ, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

Examples

Example 1

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]

Explanation:

• At time 0, person 0 shares the secret with person 1.
• At time 5, person 1 shares the secret with person 2.
• At time 8, person 2 shares the secret with person 3.
• At time 10, person 1 shares the secret with person 5.

Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2

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

Explanation:

• At time 0, person 0 shares the secret with person 3.
• At time 2, neither person 1 nor person 2 know the secret.
• At time 3, person 3 shares the secret with person 0 and person 1.

Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3

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

Explanation:

• At time 0, person 0 shares the secret with person 1.
• At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3 (the secret can be passed within the same time frame).
• At time 2, person 3 shares the secret with person 4.

Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

Constraints

• `2 $a[2] $b[2]);

  // Union‑Find data structures. $parent = range(0, $n - 1); $size = array_fill(0, $n, 1);

  // Helper functions. $find = function (int $x) use (&$parent, &$find): int { if ($parent[$x] !== $x) { $parent[$x] = $find($parent[$x]); // Path compression. } return $parent[$x]; };

  $union = function (int $a, int $b) use (&$parent, &$size, $find): void { $ra = $find($a); $rb = $find($b); if ($ra === $rb) return; // Union by size. if ($size[$ra]

## Complexity Analysis  

- **Time Complexity:**  
  Sorting the meetings takes `O(m log m)` where `m = meetings.length`.  
  Processing each meeting involves near‑constant amortized union‑find operations, giving `O(m α(n))`, where `α` is the inverse Ackermann function (practically constant).  

- **Space Complexity:**  
  `O(n + m)` for the union‑find arrays and the grouped meetings.