The earliest moment when everyone become friends

Array Union-Find Sorting

66.0% acceptance

Mar 31, 2026

1115

There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestampi. Friendship is symmetric. That means if a is friends with b, then b is friends with a. Also, person a is acquainted with a person b if a is friends with b, or a is a friend of someone acquainted with b. Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return -1.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn earliest_acq(mut logs: Vec<Vec<i32>>, n: i32) -> i32 {
    logs.sort_unstable_by_key(|l| l[0]);
    let n = n as usize;
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0u8; n];
    let mut components = n;

    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x {
        parent[x] = find(parent, parent[x]);
      }
      parent[x]
    }

    for log in &logs {
      let (t, a, b) = (log[0], log[1] as usize, log[2] as usize);
      let ra = find(&mut parent, a);
      let rb = find(&mut parent, b);
      if ra != rb {
        if rank[ra] < rank[rb] {
          parent[ra] = rb;
        } else if rank[ra] > rank[rb] {
          parent[rb] = ra;
        } else {
          parent[rb] = ra;
          rank[ra] += 1;
        }
        components -= 1;
        if components == 1 {
          return t;
        }
      }
    }
    -1
  }
}