The Earliest Moment When Everyone Become Friends

medium union find graph sorting

Problem

There are n people; logs[i] = [timestamp, a, b] means a and b became friends at timestamp. Friendship is transitive. Return the earliest timestamp at which everyone is connected, or -1 if it never happens.

Inputlogs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4

Output3

At time 3, people {0,1,2,3} are all linked through one tree.

logs (semicolon-separated [t,a,b])

def earliest_acq(logs, n):
    logs.sort(key=lambda x: x[0])
    parent = list(range(n))
    comps = n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for t, a, b in logs:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            comps -= 1
            if comps == 1:
                return t
    return -1

function earliestAcq(logs, n) {
  logs.sort((a, b) => a[0] - b[0]);
  const parent = Array.from({length: n}, (_, i) => i);
  let comps = n;
  function find(x) {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
  }
  for (const [t, a, b] of logs) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) {
      parent[ra] = rb;
      comps--;
      if (comps === 1) return t;
    }
  }
  return -1;
}

class Solution {
    int[] parent;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    public int earliestAcq(int[][] logs, int n) {
        Arrays.sort(logs, (a, b) -> a[0] - b[0]);
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int comps = n;
        for (int[] log : logs) {
            int ra = find(log[1]), rb = find(log[2]);
            if (ra != rb) { parent[ra] = rb; if (--comps == 1) return log[0]; }
        }
        return -1;
    }
}

int earliestAcq(vector<vector<int>>& logs, int n) {
    sort(logs.begin(), logs.end());
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
    int comps = n;
    for (auto& l : logs) {
        int ra = find(l[1]), rb = find(l[2]);
        if (ra != rb) { parent[ra] = rb; if (--comps == 1) return l[0]; }
    }
    return -1;
}

Explanation

We want the earliest time when all n people are connected through friendships. Because friendships pile up over time and never disappear, the smart move is to process the logs in time order and merge people as each friendship forms.

This is a perfect fit for union-find. We start with n separate components (everyone alone) and keep a counter comps. Each time we union two people who were in different groups, the number of components drops by one.

The instant comps reaches 1, everyone is in a single connected group, and the timestamp of that log is the answer. If we run out of logs and still have more than one group, we return -1.

find(x) follows parents to a group's root; if two people already share a root, that friendship is redundant and we skip it without changing the count.

Example: logs sorted by time, n = 4. After processing the log at t = 3, the last two groups merge so comps becomes 1 and people {0,1,2,3} are all linked — the answer is 3.

Time: O(m log m + m α(n)) Space: O(n)