Find all people with secret

Depth-First Search Breadth-First Search Union-Find Graph Theory Sorting

48.4% acceptance

Feb 25, 2026

1940

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] = [xi, yi, timei] indicates that person xi and person yi have a meeting at timei. 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 a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashMap, HashSet};


fn uf_find2(parent: &mut HashMap<usize, usize>, mut x: usize) -> usize {
  loop {
    let p = *parent.entry(x).or_insert(x);
    if p == x {
      break;
    }
    let pp = *parent.entry(p).or_insert(p);
    parent.insert(x, pp); // path halving
    x = pp;
  }
  x
}

impl Solution {
  pub fn find_all_people(n: i32, mut meetings: Vec<Vec<i32>>, first_person: i32) -> Vec<i32> {
    let n = n as usize;
    let mut known = vec![false; n];
    known[0] = true;
    known[first_person as usize] = true;

    // Sort meetings by time
    meetings.sort_unstable_by_key(|m| m[2]);

    // Process all meetings at the same time together
    let mut i = 0;
    while i < meetings.len() {
      let t = meetings[i][2];
      let mut j = i;
      while j < meetings.len() && meetings[j][2] == t {
        j += 1;
      }

      // Build union-find for participants in this time group
      let mut parent: HashMap<usize, usize> = HashMap::new();

      // Union pairs
      for k in i..j {
        let x = meetings[k][0] as usize;
        let y = meetings[k][1] as usize;
        parent.entry(x).or_insert(x);
        parent.entry(y).or_insert(y);
        let rx = uf_find2(&mut parent, x);
        let ry = uf_find2(&mut parent, y);
        if rx != ry {
          parent.insert(ry, rx);
        }
      }

      // Collect all participants
      let participants: Vec<usize> = parent.keys().cloned().collect();

      // Check which roots know the secret
      let mut root_knows: HashSet<usize> = HashSet::new();
      for &p in &participants {
        if known[p] {
          let root = uf_find2(&mut parent, p);
          root_knows.insert(root);
        }
      }

      // Spread secret to all in knowing components
      for &p in &participants {
        let root = uf_find2(&mut parent, p);
        if root_knows.contains(&root) {
          known[p] = true;
        }
      }

      i = j;
    }

    (0..n).filter(|&i| known[i]).map(|i| i as i32).collect()
  }
}