LeetCode 1101 - The Earliest Moment When Everyone Become Friends

LeetCode Problem 1101

Difficulty: 🟡 Medium
Topics: Array, Union-Find, Sorting

Solution

Problem Understanding

The problem is asking us to determine the earliest time at which a group of n people all become mutually acquainted, given a sequence of friendship formation events with timestamps. Each event [timestamp, xi, yi] indicates that person xi and person yi become friends at that exact moment. Friendship is symmetric, meaning if xi is friends with yi, then yi is friends with xi. Additionally, friendship is transitive in this problem: if xi is friends with yi and yi is friends with zi, then xi and zi are also considered acquainted.

The input consists of a list logs of length up to 10^4, where each element is a triplet representing a timestamp and two distinct people forming a friendship. The timestamps are unique and range up to 10^9. The output should be the smallest timestamp at which all n people are interconnected through direct or indirect friendships. If no such timestamp exists, we return -1.

Key insights from the constraints include that n is relatively small (n <= 100) but the number of events can be large (logs.length <= 10^4). This suggests that a data structure capable of efficiently merging groups, like Union-Find, is appropriate. The uniqueness of timestamps simplifies ordering, as sorting the events by timestamp is straightforward.

Important edge cases include scenarios where n people never become fully connected, or when events are sparse or ordered in such a way that multiple disjoint groups exist for extended periods.

Approaches

The brute-force approach involves simulating the friendships using adjacency lists or matrices and repeatedly checking connectivity across all pairs after each friendship event. While this guarantees correctness, checking full connectivity after each event would require O(n^2) time per event, leading to a total complexity of O(n^2 * m) where m is the number of logs. For n = 100 and m = 10^4, this becomes too slow.

The optimal approach uses a Union-Find (Disjoint Set Union) data structure. Each person starts in their own group, and every friendship merges the groups of the two people involved. We maintain a count of how many disjoint sets exist. When this count reaches 1, all people are connected, and the current timestamp is the earliest time when everyone becomes friends. This avoids the repeated O(n^2) connectivity checks and reduces the total runtime substantially.

Algorithm Walkthrough

1. Sort the Logs: Sort the friendship events in increasing order of timestamps. This ensures we process friendships chronologically.
2. Initialize Union-Find: Create a Union-Find structure with n elements. Each person initially belongs to their own set. Maintain a counter for the number of connected components, initially n.
3. Process Events: Iterate through the sorted logs. For each friendship [timestamp, xi, yi], perform a union operation between xi and yi.
4. Check Connectivity: After each union, check if the number of connected components has become 1. If it has, return the current timestamp since this is the earliest moment all people are connected.
5. No Complete Connection: If after processing all logs, the number of connected components is greater than 1, return -1 as not everyone became friends.

Why it works: The Union-Find maintains the invariant that each set represents a group of people who are all mutually acquainted. By counting the number of connected components, we can efficiently detect when all people are interconnected without having to check all pairs repeatedly.

Python Solution

from typing import List

class UnionFind:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size
        self.components = size

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

    def union(self, x: int, y: int) -> bool:
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        self.components -= 1
        return True

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        logs.sort(key=lambda x: x[0])
        uf = UnionFind(n)
        for timestamp, x, y in logs:
            uf.union(x, y)
            if uf.components == 1:
                return timestamp
        return -1

The UnionFind class handles the grouping efficiently. The find method applies path compression to flatten the structure, while union merges two sets by rank to keep the tree shallow. The components counter tracks the number of separate groups, allowing an immediate check for full connectivity after each union.

Go Solution

package main

import (
    "sort"
)

type UnionFind struct {
    parent     []int
    rank       []int
    components int
}

func NewUnionFind(size int) *UnionFind {
    parent := make([]int, size)
    rank := make([]int, size)
    for i := 0; i < size; i++ {
        parent[i] = i
    }
    return &UnionFind{parent, rank, size}
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
    rootX := uf.Find(x)
    rootY := uf.Find(y)
    if rootX == rootY {
        return false
    }
    if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
    uf.components--
    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 {
        timestamp, x, y := log[0], log[1], log[2]
        uf.Union(x, y)
        if uf.components == 1 {
            return timestamp
        }
    }
    return -1
}

In Go, slices and integer operations are straightforward. The main difference from Python is manual slice management and explicit constructor usage. Nil slices are not an issue here since we initialize with make.

Worked Examples

Example 1: 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.

Example 2: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4.