The Earliest Moment When Everyone Become Friends

Medium
454.

The Earliest Moment When Everyone Become Friends

The Earliest Moment When Everyone Become Friends is a medium coding problem on arrays, sorting and union find, asked in Amazon, Google and Meta interviews.

In a group of n people numbered 0 through n - 1, logs[i] = [timestamp, x, y] records that x and y became friends at that time. Friendship is mutual and transitive: friends of friends are acquainted.

Return the earliest timestamp at which everyone is acquainted with everyone else, or -1 if that never happens.

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

Example 2

Input
logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output
3

Example 3

Input
logs = [[0,0,1]], n = 3
Output
-1

Constraints

  • 1 <= n <= 40
  • 1 <= logs.length <= 60
  • All timestamps are distinct.

Follow-up: Sorting dominates the running time. Can you keep the union-find part almost linear?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} logs
 * @param {number} n
 * @return {number}
 */
var earliestAcq = function(logs, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The Earliest Moment When Everyone Become Friends — Solution

The Earliest Moment When Everyone Become Friends solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

The Earliest Moment When Everyone Become Friends is a medium coding problem on arrays, sorting and union find, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Union Find
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In a group of n people numbered 0 through n - 1, logs[i] = [timestamp, x, y] records that x and y became friends at that time. Friendship is mutual and transitive: friends of friends are acquainted.

Return the earliest timestamp at which everyone is acquainted with everyone else, or -1 if that never happens.

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

Example 2

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3

Example 3

Input: logs = [[0,0,1]], n = 3
Output: -1

Constraints

  • 1 <= n <= 40
  • 1 <= logs.length <= 60
  • All timestamps are distinct.

Follow-up: Sorting dominates the running time. Can you keep the union-find part almost linear?

Hints for The Earliest Moment When Everyone Become Friends

  1. Hint 1

    Process the friendships in chronological order, so sort the logs by timestamp first.

  2. Hint 2

    Union-find tracks how many separate groups remain, starting at n.

  3. Hint 3

    The moment the group count drops to 1 is the answer; if it never does, return -1.

How to solve The Earliest Moment When Everyone Become Friends

Process friendships in time order with union-find; the timestamp that reduces the group count to 1 is the answer.

Approach

  1. Sort logs by timestamp.
  2. For each log, union the pair; if it merges two groups and the count reaches 1, return the timestamp.
  3. Return -1 if never.

Why it works

Acquaintance is transitive closure of friendship, which is exactly the component structure; processing chronologically finds the first moment a single component forms.

Complexity

  • Time — O(m log m + m · α(n))
  • Space — O(n)

Pitfalls

  • With n = 1 everyone is already acquainted at time 0.

Reference solution

Python

def earliestAcq(logs, n: int) -> int:
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    groups = n
    for timestamp, x, y in sorted(logs):
        rx, ry = find(x), find(y)
        if rx != ry:
            parent[rx] = ry
            groups -= 1
            if groups == 1:
                return timestamp
    return 0 if groups == 1 else -1

Java

private static int findRoot(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

public static int earliestAcq(int[][] logs, int n) {
    int[][] sorted = logs.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int groups = n;
    for (int[] entry : sorted) {
        int a = findRoot(parent, entry[1]);
        int b = findRoot(parent, entry[2]);
        if (a != b) {
            parent[a] = b;
            groups--;
            if (groups == 1) return entry[0];
        }
    }
    return groups == 1 ? 0 : -1;
}

C++

static int findRoot(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int earliestAcq(vector<vector<int>>& logs, int n) {
    vector<vector<int>> sorted = logs;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
    vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    int groups = n;
    for (const auto& entry : sorted) {
        int a = findRoot(parent, entry[1]);
        int b = findRoot(parent, entry[2]);
        if (a != b) {
            parent[a] = b;
            groups--;
            if (groups == 1) return entry[0];
        }
    }
    return groups == 1 ? 0 : -1;
}

JavaScript

var earliestAcq = function(logs, n) {
    const sorted = logs.slice().sort(function(a, b) { return a[0] - b[0]; });
    const parent = [];
    for (let i = 0; i < n; i++) parent.push(i);
    const find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    let groups = n;
    for (let i = 0; i < sorted.length; i++) {
        const a = find(sorted[i][1]);
        const b = find(sorted[i][2]);
        if (a !== b) {
            parent[a] = b;
            groups--;
            if (groups === 1) return sorted[i][0];
        }
    }
    return groups === 1 ? 0 : -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms