LeetCode 1101. The Earliest Moment When Everyone Become Friends Solution
There are n people in a social group labeled from to . You are given an array logs
where logs[i]
= [, , ] indicates that and will be friends at the time .
Friendship is symmetric. That means if is friends with , then is friends with . Also, person is acquainted with a person if is friends with , or is a friend of someone acquainted with .
Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return .
Example 1:
Input: 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
Output:
Explanation:
The first event occurs at timestamp = 20190101
and after and become friends we have the following friendship groups [0,1], [2], [3], [4], [5]
.
The second event occurs at timestamp = 20190104
and after and become friends we have the following friendship groups [0,1], [2], [3,4], [5]
.
The third event occurs at timestamp = 20190107
and after and become friends we have the following friendship groups [0,1], [2,3,4], [5]
.
The fourth event occurs at timestamp = 20190211
and after and become friends we have the following friendship groups [0,1,5], [2,3,4]
.
The fifth event occurs at timestamp = 20190224
and as and are already friends anything happens.
The sixth event occurs at timestamp = 20190301
and after and become friends we have that all become friends.
Example 2:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]]
, n = 4
Output:
Constraints:
-
logs.length
logs[i].length == 3
- All the values are unique.
- All the pairs occur at most one time in the input.
Problem Link: https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/
Solution
Brute Force
When we see problems related to connectivity, we should think of applying DSU. This problem asks us to find the first instance where the graph formed by friendships is connected. To accomplish this, we'll first sort the friendships by . Then, we'll iterate through friendships from the least to greatest and merge nodes connected by a friendship until the graph is connected.
After each iteration, we'll check if the graph is connected and return the timestamp value if it is. An easy way to check if the graph is connected is to check if node is connected to all other nodes. If the graph isn't connected after processing all the friendships, we'll return .
Let's denote the number of friendships(edges) as .
Since checking the connectivity of the graph is and we do this times, this solution runs in .
Full Solution
Since checking the connectivity of the graph is too inefficient, we'll maintain the number of components in the graph as we include more and more friendships. We can make the observation that every time we merge two disjoint sets, the number of components decreases by . This is true as this operation turns disjoint sets into disjoint set without disturbing any other disjoint sets. We initially start with components (one for each person) and once we reach one component, we'll return the respective timestamp value. will be returned if we never reach one component.
Time Complexity
Sorting takes and the main algorithm runs in . Thus our time complexity is .
Time Complexity:
Bonus: We can also use union by rank mentioned here to improve the time complexity of DSU operations from to .
Space Complexity
Our DSU uses memory.
Space Complexity: .
C++ Solution
1class Solution {
2 public:
3 vector<int> parent;
4 int find(int x) { // finds the id/leader of a node
5 if (parent[x] == x) {
6 return x;
7 }
8 parent[x] = find(parent[x]);
9 return parent[x];
10 }
11 void Union(int x, int y) { // merges two disjoint sets into one set
12 x = find(x);
13 y = find(y);
14 parent[x] = y;
15 }
16 static bool comp(vector<int>& a, vector<int>& b) { // sorting comparator
17 return a[0] < b[0];
18 }
19 int earliestAcq(vector<vector<int>>& logs, int n) {
20 parent.resize(n);
21 for (int i = 0; i < n; i++) {
22 parent[i] = i;
23 }
24 sort(logs.begin(), logs.end(), comp); // sorts friendships by timestamp
25 int components = n;
26 for (vector<int> friendship : logs) {
27 int timestamp = friendship[0];
28 int x = friendship[1];
29 int y = friendship[2];
30 if (find(x) != find(y)) { // merge two disjoint sets
31 Union(x, y);
32 components--;
33 }
34 if (components == 1) { // reached connected graph
35 return timestamp;
36 }
37 }
38 return -1;
39 }
40};
Java Solution
1class Solution {
2 private int find(int x, int[] parent) { // finds the id/leader of a node
3 if (parent[x] == x) {
4 return x;
5 }
6 parent[x] = find(parent[x], parent);
7 return parent[x];
8 }
9 private void Union(int x, int y, int[] parent) { // merges two disjoint sets into one set
10 x = find(x, parent);
11 y = find(y, parent);
12 parent[x] = y;
13 }
14
15 public int earliestAcq(int[][] logs, int n) {
16 int[] parent = new int[n];
17 for (int i = 0; i < n; i++) {
18 parent[i] = i;
19 }
20 Arrays.sort(logs, (a, b) -> a[0] - b[0]); // sorts friendships by timestamp
21 int components = n;
22 for (int[] friendship : logs) {
23 int timestamp = friendship[0];
24 int x = friendship[1];
25 int y = friendship[2];
26 if (find(x, parent) != find(y, parent)) { // merge two disjoint sets
27 Union(x, y, parent);
28 components--;
29 }
30 if (components == 1) { // reached connected graph
31 return timestamp;
32 }
33 }
34 return -1;
35 }
36}
Python Solution
1class Solution: 2 def earliestAcq(self, logs: List[List[int]], n: int) -> int: 3 parent = [i for i in range(n)] 4 5 def find(x): # finds the id/leader of a node 6 if parent[x] == x: 7 return x 8 parent[x] = find(parent[x]) 9 return parent[x] 10 11 def Union(x, y): # merges two disjoint sets into one set 12 x = find(x) 13 y = find(y) 14 parent[x] = y 15 16 logs.sort(key=lambda x: x[0]) # sorts friendships by timestamp 17 components = n 18 for friendship in logs: 19 timestamp = friendship[0] 20 x = friendship[1] 21 y = friendship[2] 22 if find(x) != find(y): # merge two disjoint sets 23 Union(x, y) 24 components -= 1 25 if components == 1: # reached connected graph 26 return timestamp 27 return -1 28