The Earliest Moment When Everyone Become Friends

The Earliest Moment When Everyone Become Friends - Problem

There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestamp_i, x_i, y_i] indicates that x_i and y_i will be friends at the time timestamp_i.

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.

Input & Output

Example 1 — Basic Case

$ Input: logs = [[20,0,1],[5,2,3],[15,3,4],[18,0,2]], n = 5

› Output: 20

💡 Note: At time 5: {2,3} connected. At time 15: {2,3,4} connected. At time 18: {0,2,3,4} connected. At time 20: {0,1,2,3,4} all connected - everyone knows everyone!

Example 2 — Already Connected

$ Input: logs = [[0,1,0],[1,0,1]], n = 2

› Output: 0

💡 Note: At time 0, persons 0 and 1 become friends, so everyone is connected immediately

Example 3 — Impossible Case

$ Input: logs = [[0,0,1],[2,1,2]], n = 4

› Output: -1

💡 Note: Person 3 never gets connected to anyone, so it's impossible for everyone to be connected

Constraints

2 ≤ n ≤ 100
1 ≤ logs.length ≤ 10⁴
logs[i].length == 3
0 ≤ logs[i][1], logs[i][2] ≤ n - 1
logs[i][0] ≤ 10⁹
logs[i][1] ≠ logs[i][2]

Visualization

Tap to expand

Understanding the Visualization

Input

Friendship logs with timestamps and people pairs

Process

Sort by time and track connected components

Output

Timestamp when everyone is in one group

Key Takeaway

🎯 Key Insight: Use Union-Find to efficiently track when separate friend groups merge into one big connected community

Asked in

f Facebook 25 G Google 15

The key insight is to use Union-Find to efficiently track connected components as friendships form over time. Sort events by timestamp and merge components using union operations. Return the timestamp when all people form one connected component. Best approach: Union-Find with Time: O(m log m + mα(n)), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find (Disjoint Set Union)	O(m log m + mα(n))	O(n)	Use Union-Find data structure to efficiently track connected components
Brute Force with DFS	O(m × n²)	O(n²)	For each timestamp, build graph and check if all nodes are connected using DFS

Union-Find (Disjoint Set Union) — Algorithm Steps

Sort logs by timestamp
Initialize Union-Find with n components
For each friendship, union the two people
Return timestamp when components count reaches 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Each person starts as their own component

Union Operation

Merge components when friendship forms

Check Count

Return timestamp when components = 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* parent;
    int* rank;
    int components;
    int n;
} UnionFind;

UnionFind* createUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->parent = (int*)malloc(n * sizeof(int));
    uf->rank = (int*)calloc(n, sizeof(int));
    uf->components = n;
    uf->n = n;
    
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
    }
    
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

int unionSets(UnionFind* uf, int x, int y) {
    int px = find(uf, x);
    int py = find(uf, y);
    
    if (px == py) return 0;
    
    if (uf->rank[px] < uf->rank[py]) {
        int temp = px;
        px = py;
        py = temp;
    }
    
    uf->parent[py] = px;
    if (uf->rank[px] == uf->rank[py]) {
        uf->rank[px]++;
    }
    
    uf->components--;
    return 1;
}

void freeUnionFind(UnionFind* uf) {
    free(uf->parent);
    free(uf->rank);
    free(uf);
}

int compare(const void* a, const void* b) {
    int* logA = (int*)a;
    int* logB = (int*)b;
    return logA[0] - logB[0];
}

int solution(int** logs, int logsSize, int* logsColSize, int n) {
    if (n <= 1) return n == 1 ? 0 : -1;
    
    qsort(logs, logsSize, sizeof(int*), compare);
    UnionFind* uf = createUnionFind(n);
    
    for (int i = 0; i < logsSize; i++) {
        int timestamp = logs[i][0];
        int x = logs[i][1];
        int y = logs[i][2];
        
        unionSets(uf, x, y);
        if (uf->components == 1) {
            int result = timestamp;
            freeUnionFind(uf);
            return result;
        }
    }
    
    freeUnionFind(uf);
    return -1;
}

int main() {
    // Simplified input parsing for C
    int logs[][3] = {{20,0,1}, {5,2,3}, {15,3,4}, {18,0,2}};
    int* logPtrs[] = {logs[0], logs[1], logs[2], logs[3]};
    int logsColSize[] = {3,3,3,3};
    int n = 5;
    
    int result = solution(logPtrs, 4, logsColSize, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m log m + mα(n))

O(m log m) for sorting logs, O(mα(n)) for m union operations with inverse Ackermann

⚡ Linearithmic

Space Complexity

O(n)

Union-Find parent and rank arrays each store n elements

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find (Disjoint Set Union) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler