Pseudo-code

text
function earliestAcq(logs, n):
    sort logs by timestamp
    graph = new AdjacencyList(n)
    
    for each (t, x, y) in logs:
        graph.addEdge(x, y)
        visited_count = performBFS(graph, start_node=0)
        if visited_count == n:
            return t
            
    return -1

Complexity & Limitations

• Time Complexity: $O(M \cdot (N + M))$, where $M$ is the number of logs. Sorting takes $O(M \log M)$. The loop runs $M$ times, and inside the loop, a BFS takes $O(N + E)$, where $E$ is the number of edges added so far (up to $M$). This results in quadratic behavior relative to the number of logs.
• Why it fails: While this might pass for small $N$ ($N \le 100$), it is highly inefficient. We are re-scanning the entire graph structure to verify connectivity after adding a single edge. This redundant work makes the solution unscalable for larger datasets or stricter time limits.

Core Insight for The Earliest Moment When Everyone Become Friends

The key intuition lies in viewing each person as an isolated island initially. As we process friendship logs, we build bridges between these islands.

Instead of running a full traversal to check if all islands are connected, we can maintain a count of connected components.

1. Initially, there are $N$ people, so there are $N$ independent components.
2. When a friendship $(x, y)$ occurs, we check if $x$ and $y$ are already in the same component.
3. If they are in different components, we union (merge) them. This action effectively reduces the total number of components by exactly 1.
4. If they are already in the same component, the number of components remains unchanged (the edge is redundant for connectivity).

The moment the number of components drops to 1, we know everyone is connected. Since we process logs in increasing order of timestamps, the first time this counter hits 1 corresponds to the earliest possible moment.

Visual Description: Imagine a forest of $N$ trees, where each node is a root of its own tree. The parent array tracks these relationships.

• Initially, parent[i] = i for all $i$.
• When we merge node A and node B, we find the root of A and the root of B. We make one root the child of the other.
• Visually, two separate trees become one larger tree.
• We stop the algorithm immediately when the forest contains only a single tree.

Algorithm Strategy: Graph - Union-Find (Disjoint Set Union - DSU)

To implement the optimal solution for LeetCode 1101, we utilize the DSU data structure with Path Compression and Union by Rank (or Size) for near-constant time operations.

1. Preprocessing: Sort the logs array based on timestamps. This is critical because the problem asks for the earliest moment.
2. Initialization: Create a DSU structure.
   • parent array of size $N$, initialized such that parent[i] = i.
   • rank array (optional but recommended) to optimize tree height.
   • component_count variable initialized to $N$.
3. Processing: Iterate through the sorted logs. For each friendship between x and y at time t:
   • Find the root representative of x (rootX) and y (rootY).
   • If rootX != rootY, perform a Union operation:
     • Link the two sets (e.g., make rootY the parent of rootX).
     • Decrement component_count by 1.
   • Immediately after decrementing, check if component_count == 1.
   • If yes, return t.
4. Termination: If the loop completes and component_count is still greater than 1, return -1 (meaning the group never fully connected).

Execution Flow

Let's trace the algorithm with $N=4$ and logs: [[20190101, 0, 1], [20190104, 3, 0], [20190107, 2, 3]].

1. Sort Logs: The logs are already sorted by time.
2. Init:
   • parent = [0, 1, 2, 3]
   • components = 4
3. Process Log 1: [20190101, 0, 1]
   • Find(0) $\to$ 0. Find(1) $\to$ 1.
   • Roots are different. Union(0, 1).
   • parent becomes [1, 1, 2, 3] (0 points to 1).
   • components becomes 3.
   • Check: $3 \neq 1$. Continue.
4. Process Log 2: [20190104, 3, 0]
   • Find(3) $\to$ 3. Find(0) $\to$ 1 (via path compression).
   • Roots are 3 and 1. Different. Union(3, 1).
   • parent becomes [1, 1, 2, 1] (3 points to 1).
   • components becomes 2.
   • Check: $2 \neq 1$. Continue.
5. Process Log 3: [20190107, 2, 3]
   • Find(2) $\to$ 2. Find(3) $\to$ 1.
   • Roots are 2 and 1. Different. Union(2, 1).
   • parent becomes [1, 1, 1, 1] (2 points to 1).
   • components becomes 1.
   • Check: $1 == 1$. .

Proof of Correctness

The correctness relies on two properties:

1. Chronological Order: By sorting logs, we guarantee that we process connections in the exact order they occurred in time. The first time the condition (fully connected) is met, it corresponds to the minimum timestamp.
2. Component Invariant: The DSU structure correctly maintains the invariant that component_count equals the number of disjoint sets in the graph. Since we start with $N$ sets and only decrement when two previously disjoint sets merge, component_count == 1 is the necessary and sufficient condition for full connectivity.

Reference Implementation

C++ Solution for LeetCode 1101

cpp
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class Solution {
    struct DSU {
        vector<int> parent;
        vector<int> rank;
        int components;

        DSU(int n) {
            parent.resize(n);
            // Initialize parent pointers to self
            iota(parent.begin(), parent.end(), 0);
            rank.assign(n, 0);
            components = n;
        }

        int find(int x) {
            if (parent[x] != x) {
                // Path compression
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        bool unite(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX != rootY) {
                // Union by rank
                if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                components--;
                return true;
            }
            return false;
        }
    };

public:
    int earliestAcq(vector<vector<int>>& logs, int n) {
        // Sort logs by timestamp
        sort(logs.begin(), logs.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

        DSU dsu(n);

        for (const auto& log : logs) {
            int timestamp = log[0];
            int person1 = log[1];
            int person2 = log[2];

            if (dsu.unite(person1, person2)) {
                if (dsu.components == 1) {
                    return timestamp;
                }
            }
        }

        return -1;
    }
};

Java Solution for LeetCode 1101

java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    class DSU {
        int[] parent;
        int[] rank;
        int components;

        public DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            components = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                // Path compression
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX != rootY) {
                // Union by rank
                if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                components--;
                return true;
            }
            return false;
        }
    }

    public int earliestAcq(int[][] logs, int n) {
        // Sort logs by timestamp (index 0)
        Arrays.sort(logs, Comparator.comparingInt(a -> a[0]));

        DSU dsu = new DSU(n);

        for (int[] log : logs) {
            int timestamp = log[0];
            int x = log[1];
            int y = log[2];

            // Attempt to union the two people
            if (dsu.union(x, y)) {
                // If components drop to 1, everyone is connected
                if (dsu.components == 1) {
                    return timestamp;
                }
            }
        }

        return -1;
    }
}

Python Solution for LeetCode 1101

python
class Solution:
    def earliestAcq(self, logs: list[list[int]], n: int) -> int:
        # Sort logs by timestamp
        logs.sort(key=lambda x: x[0])
        
        parent = list(range(n))
        rank = [0] * n
        self.components = n
        
        def find(x):
            if parent[x] != x:
                # Path compression
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            rootX = find(x)
            rootY = find(y)
            
            if rootX != rootY:
                # Union by rank
                if rank[rootX] < rank[rootY]:
                    parent[rootX] = rootY
                elif rank[rootX] > rank[rootY]:
                    parent[rootY] = rootX
                else:
                    parent[rootY] = rootX
                    rank[rootX] += 1
                
                self.components -= 1
                return True
            return False

        for timestamp, x, y in logs:
            if union(x, y):
                if self.components == 1:
                    return timestamp
                    
        return -1

• Mistake: Implementing DSU without Path Compression.
• Reason: Without path compression, the find operation can degrade to $O(N)$ in the worst case (a skewed tree), making the total complexity $O(M \cdot N)$.
• Consequence: Efficiency failure on large datasets ($M=10^4$).