logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
2. Add Two Numbers3. Longest Substring Without Repeating Characters5. Longest Palindromic Substring8. String to Integer (atoi)11. Container With Most Water15. 3Sum17. Letter Combinations of a Phone Number19. Remove Nth Node From End of List22. Generate Parentheses33. Search in Rotated Sorted Array34. Find First and Last Position of Element in Sorted Array48. Rotate Image49. Group Anagrams50. Pow(x, n)53. Maximum Subarray54. Spiral Matrix56. Merge Intervals61. Rotate List73. Set Matrix Zeroes74. Search a 2D Matrix75. Sort Colors78. Subsets137. Single Number II138. Copy List with Random Pointer150. Evaluate Reverse Polish Notation151. Reverse Words in a String153. Find Minimum in Rotated Sorted Array155. Min Stack162. Find Peak Element169. Majority Element198. House Robber207. Course Schedule215. Kth Largest Element in an Array227. Basic Calculator II236. Lowest Common Ancestor of a Binary Tree237. Delete Node in a Linked List238. Product of Array Except Self451. Sort Characters By Frequency540. Single Element in a Sorted Array560. Subarray Sum Equals K636. Exclusive Time of Functions875. Koko Eating Bananas1011. Capacity To Ship Packages Within D Days1101. The Earliest Moment When Everyone Become Friends1283. Find the Smallest Divisor Given a Threshold2140. Solving Questions With Brainpower3169. Count Days Without Meetings3481. Apply Substitutions
Code Scratch/leetcode/medium

1101. The Earliest Moment When Everyone Become Friends

2 min read
On this pageIntuition
IntuitionComplexityCode

# Intuition

This problem is about determining when a group of people becomes fully connected through friendships. Since friendships can spread indirectly (via mutual acquaintances), we can model the network using Union-Find (Disjoint Set Union). Each person starts in their own group, and as we process friendship logs (sorted by time), we gradually merge these groups. When there's only one group left, everyone is connected.

# Complexity

Space ComplexityTime Complexity
O(1)\text{O}(1)O(1)O(L∗log⁡L+L∗N)\text{O}(L*\log{L} + L*N)O(L∗logL+L∗N)

# Code

class UnionFind {
    int[] parent;
    int[] rank;
 
    // Initialize Union-Find data structure
    UnionFind(int totalPeople) {
        parent = new int[totalPeople];
        rank = new int[totalPeople];
 
        for (int i = 0; i < totalPeople; ++i) {
            parent[i] = i;  // Each person is initially their own parent
            rank[i] = 0;    // Initial rank is zero
        }
    }
 
    // Find the representative (root parent) of the given node
    public int findRepresentative(int person) {
        int representative = parent[person];
 
        // Path compression for efficiency
        while (representative != parent[representative]) {
            representative = parent[representative];
        }
 
        // Directly link the current node to its root parent
        parent[person] = representative;
 
        return representative;
    }
 
    // Union two groups (friend circles)
    public void union(int personA, int personB) {
        int repA = findRepresentative(personA);
        int repB = findRepresentative(personB);
 
        // If they already belong to the same group, do nothing
        if (repA == repB) return;
 
        // Union by rank to maintain a shallow tree
        if (rank[repA] > rank[repB]) {
            parent[repB] = repA;
        } else if (rank[repA] < rank[repB]) {
            parent[repA] = repB;
        } else {
            parent[repA] = repB;
            rank[repB]++;
        }
    }
 
    // Check if all people share the same parent (i.e., are fully connected)
    public boolean areAllConnected() {
        int rootParent = -1;
 
        for (int i = 0; i < parent.length; ++i) {
            int currentParent = findRepresentative(i);
 
            if (rootParent != -1 && rootParent != currentParent) {
                return false;
            }
 
            rootParent = currentParent;
        }
 
        return true;
    }
}
 
public int earliestAcq(int[][] logs, int totalPeople) {
    // Sort logs by timestamp to simulate events in order
    Arrays.sort(logs, (log1, log2) -&gt; Integer.compare(log1[0], log2[0]));
 
    UnionFind unionFind = new UnionFind(totalPeople);
 
    // Process each friendship log
    for (int i = 0; i < logs.length; ++i) {
        int timestamp = logs[i][0];
        int personX = logs[i][1];
        int personY = logs[i][2];
 
        // Union the two people
        unionFind.union(personX, personY);
 
        // Check if everyone is now connected
        if (unionFind.areAllConnected()) {
            return timestamp;
        }
    }
 
    // Not all people became friends
    return -1;
}
 
←Previous1011. Capacity To Ship Packages Within D DaysNext→1283. Find the Smallest Divisor Given a Threshold

On this page

IntuitionComplexityCode