Question

1101. The Earliest Moment When Everyone Become Friends

中文文档

Description

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.

 

Example 1:

Input: logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], n = 6
Output: 20190301
Explanation: 
The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5].
The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5].
The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5].
The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4].
The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens.
The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.

Example 2:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

 

Constraints:

• 2 <= n <= 100
• 1 <= logs.length <= 104
• logs[i].length == 3
• 0 <= timestampi <= 109
• 0 <= xi, yi <= n - 1
• xi != yi
• All the values timestampi are unique.
• All the pairs (xi, yi) occur at most one time in the input.

Solutions

Solution 1: Sorting + Union-Find

We sort all the logs in ascending order by timestamp, then traverse the sorted logs. Using a union-find set, we check whether the two people in the current log are already friends. If they are not friends, we merge them into one friend circle, until everyone is in one friend circle, then return the timestamp of the current log.

If we have traversed all the logs and not everyone is in one friend circle, then return $-1$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of logs.

class Solution:
  def earliestAcq(self, logs: List[List[int]], n: int) -> int:
    def find(x):
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    p = list(range(n))
    for t, x, y in sorted(logs):
      if find(x) == find(y):
        continue
      p[find(x)] = find(y)
      n -= 1
      if n == 1:
        return t
    return -1

class Solution {
  private int[] p;

  public int earliestAcq(int[][] logs, int n) {
    Arrays.sort(logs, (a, b) -> a[0] - b[0]);
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    for (int[] log : logs) {
      int t = log[0], x = log[1], y = log[2];
      if (find(x) == find(y)) {
        continue;
      }
      p[find(x)] = find(y);
      if (--n == 1) {
        return t;
      }
    }
    return -1;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

class Solution {
public:
  int earliestAcq(vector<vector<int>>& logs, int n) {
    sort(logs.begin(), logs.end());
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
      return p[x] == x ? x : p[x] = find(p[x]);
    };
    for (auto& log : logs) {
      int x = find(log[1]);
      int y = find(log[2]);
      if (x != y) {
        p[x] = y;
        --n;
      }
      if (n == 1) {
        return log[0];
      }
    }
    return -1;
  }
};

func earliestAcq(logs [][]int, n int) int {
  sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
  p := make([]int, n)
  for i := range p {
    p[i] = i
  }
  var find func(int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  for _, log := range logs {
    t, x, y := log[0], log[1], log[2]
    if find(x) == find(y) {
      continue
    }
    p[find(x)] = find(y)
    n--
    if n == 1 {
      return t
    }
  }
  return -1
}

function earliestAcq(logs: number[][], n: number): number {
  const p: number[] = Array(n)
    .fill(0)
    .map((_, i) => i);
  const find = (x: number): number => {
    if (p[x] !== x) {
      p[x] = find(p[x]);
    }
    return p[x];
  };
  logs.sort((a, b) => a[0] - b[0]);
  for (const [t, x, y] of logs) {
    const rx = find(x);
    const ry = find(y);
    if (rx !== ry) {
      p[rx] = ry;
      if (--n === 1) {
        return t;
      }
    }
  }
  return -1;
}

struct UnionFind {
  p: Vec<usize>,
  size: Vec<usize>,
}

impl UnionFind {
  fn new(n: usize) -> Self {
    let p: Vec<usize> = (0..n).collect();
    let size = vec![1; n];
    UnionFind { p, size }
  }

  fn find(&mut self, x: usize) -> usize {
    if self.p[x] != x {
      self.p[x] = self.find(self.p[x]);
    }
    self.p[x]
  }

  fn union(&mut self, a: usize, b: usize) -> bool {
    let pa = self.find(a);
    let pb = self.find(b);
    if pa == pb {
      false
    } else if self.size[pa] > self.size[pb] {
      self.p[pb] = pa;
      self.size[pa] += self.size[pb];
      true
    } else {
      self.p[pa] = pb;
      self.size[pb] += self.size[pa];
      true
    }
  }
}

impl Solution {
  pub fn earliest_acq(logs: Vec<Vec<i32>>, n: i32) -> i32 {
    let mut logs = logs;
    logs.sort_by(|a, b| a[0].cmp(&b[0]));
    let mut uf = UnionFind::new(n as usize);
    let mut n = n;
    for log in logs {
      let t = log[0];
      let x = log[1] as usize;
      let y = log[2] as usize;
      if uf.union(x, y) {
        n -= 1;
        if n == 1 {
          return t;
        }
      }
    }
    -1
  }
}

Solution 2

class UnionFind:
  __slots__ = ('p', 'size')

  def __init__(self, n):
    self.p = list(range(n))
    self.size = [1] * n

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

  def union(self, a: int, b: int) -> bool:
    pa, pb = self.find(a), self.find(b)
    if pa == pb:
      return False
    if self.size[pa] > self.size[pb]:
      self.p[pb] = pa
      self.size[pa] += self.size[pb]
    else:
      self.p[pa] = pb
      self.size[pb] += self.size[pa]
    return True


class Solution:
  def earliestAcq(self, logs: List[List[int]], n: int) -> int:
    uf = UnionFind(n)
    for t, x, y in sorted(logs):
      if uf.union(x, y):
        n -= 1
        if n == 1:
          return t
    return -1

class UnionFind {
  private int[] p;
  private int[] size;

  public UnionFind(int n) {
    p = new int[n];
    size = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      size[i] = 1;
    }
  }

  public int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }

  public boolean union(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
      return false;
    }
    if (size[pa] > size[pb]) {
      p[pb] = pa;
      size[pa] += size[pb];
    } else {
      p[pa] = pb;
      size[pb] += size[pa];
    }
    return true;
  }
}

class Solution {
  public int earliestAcq(int[][] logs, int n) {
    Arrays.sort(logs, (a, b) -> a[0] - b[0]);
    UnionFind uf = new UnionFind(n);
    for (int[] log : logs) {
      int t = log[0], x = log[1], y = log[2];
      if (uf.union(x, y) && --n == 1) {
        return t;
      }
    }
    return -1;
  }
}

class UnionFind {
public:
  UnionFind(int n) {
    p = vector<int>(n);
    size = vector<int>(n, 1);
    iota(p.begin(), p.end(), 0);
  }

  bool unite(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
      return false;
    }
    if (size[pa] > size[pb]) {
      p[pb] = pa;
      size[pa] += size[pb];
    } else {
      p[pa] = pb;
      size[pb] += size[pa];
    }
    return true;
  }

  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }

private:
  vector<int> p, size;
};

class Solution {
public:
  int earliestAcq(vector<vector<int>>& logs, int n) {
    sort(logs.begin(), logs.end());
    UnionFind uf(n);
    for (auto& log : logs) {
      int t = log[0], x = log[1], y = log[2];
      if (uf.unite(x, y) && --n == 1) {
        return t;
      }
    }
    return -1;
  }
};

type unionFind struct {
  p, size []int
}

func newUnionFind(n int) *unionFind {
  p := make([]int, n)
  size := make([]int, n)
  for i := range p {
    p[i] = i
    size[i] = 1
  }
  return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
  if uf.p[x] != x {
    uf.p[x] = uf.find(uf.p[x])
  }
  return uf.p[x]
}

func (uf *unionFind) union(a, b int) bool {
  pa, pb := uf.find(a), uf.find(b)
  if pa == pb {
    return false
  }
  if uf.size[pa] > uf.size[pb] {
    uf.p[pb] = pa
    uf.size[pa] += uf.size[pb]
  } else {
    uf.p[pa] = pb
    uf.size[pb] += uf.size[pa]
  }
  return true
}

func earliestAcq(logs [][]int, n int) int {
  sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
  uf := newUnionFind(n)
  for _, log := range logs {
    t, x, y := log[0], log[1], log[2]
    if uf.union(x, y) {
      n--
      if n == 1 {
        return t
      }
    }
  }
  return -1
}

class UnionFind {
  private p: number[];
  private size: number[];

  constructor(n: number) {
    this.p = Array(n)
      .fill(0)
      .map((_, i) => i);
    this.size = Array(n).fill(1);
  }

  find(x: number): number {
    if (this.p[x] !== x) {
      this.p[x] = this.find(this.p[x]);
    }
    return this.p[x];
  }

  union(a: number, b: number): boolean {
    const pa = this.find(a);
    const pb = this.find(b);
    if (pa === pb) {
      return false;
    }
    if (this.size[pa] > this.size[pb]) {
      this.p[pb] = pa;
      this.size[pa] += this.size[pb];
    } else {
      this.p[pa] = pb;
      this.size[pb] += this.size[pa];
    }
    return true;
  }
}

function earliestAcq(logs: number[][], n: number): number {
  logs.sort((a, b) => a[0] - b[0]);
  const uf = new UnionFind(n);
  for (const [t, x, y] of logs) {
    if (uf.union(x, y) && --n === 1) {
      return t;
    }
  }
  return -1;
}