LeetCode 1101: The Earliest Moment When Everyone Become Friends Solution

Master LeetCode problem 1101 (The Earliest Moment When Everyone Become Friends), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1101. The Earliest Moment When Everyone Become Friends

Medium

Array Union Find Sorting

Problem Explanation

Explanation:

To solve this problem, we can use the concept of Union-Find (Disjoint Set Union) data structure. We will keep track of the number of connected components as we merge the friends. If at any point the number of connected components becomes 1, it means all the friends have become friends with each other, and we return the time at which this happens.

Initialize the parent array where each friend is their own parent initially.
Initialize a size array to keep track of the size of each group.
Iterate through the timestamps in ascending order and merge the groups to which the friends belong.
Keep track of the number of connected components and return the time when it reaches 1.

Time Complexity: O(n + t * α(n)), where n is the number of friends and t is the number of timestamps. α(n) is the inverse Ackermann function, which is very slow-growing and can be considered constant in practical cases. Space Complexity: O(n) :

Solution Code

class Solution {
    public int earliestAcq(int[][] logs, int n) {
        Arrays.sort(logs, (a, b) -> a[0] - b[0]);
        int[] parent = new int[n];
        int[] size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int components = n;
        for (int[] log : logs) {
            int timestamp = log[0];
            int friend1 = log[1];
            int friend2 = log[2];
            int parent1 = find(parent, friend1);
            int parent2 = find(parent, friend2);
            if (parent1 != parent2) {
                if (size[parent1] < size[parent2]) {
                    int temp = parent1;
                    parent1 = parent2;
                    parent2 = temp;
                }
                parent[parent2] = parent1;
                size[parent1] += size[parent2];
                components--;
                if (components == 1) {
                    return timestamp;
                }
            }
        }
        return -1;
    }
    
    private int find(int[] parent, int friend) {
        if (parent[friend] != friend) {
            parent[friend] = find(parent, parent[friend]);
        }
        return parent[friend];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1101 (The Earliest Moment When Everyone Become Friends)?

This page provides optimized solutions for LeetCode problem 1101 (The Earliest Moment When Everyone Become Friends) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1101 (The Earliest Moment When Everyone Become Friends)?

The time complexity for LeetCode 1101 (The Earliest Moment When Everyone Become Friends) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1101 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1101 in Java, C++, or Python.

Back to LeetCode Solutions