1101. The Earliest Moment When Everyone Become Friends

There are n people in a social group labeled from 00 to nβˆ’1n - 1. You are given an array logs where logs[i] = [timestampi\text{timestamp}_ i, xix_i, yiy_i] indicates that xix_i and yiy_i will be friends at the time timestampi\text{timestamp}_ i.

Friendship is symmetric. That means if aa is friends with bb, then bb is friends with aa. Also, person aa is acquainted with a person bb if aa is friends with bb, or aa is a friend of someone acquainted with bb.

Return the earliest time for which every person became acquainted with every other person. If there is no such earliest time, return βˆ’1-1.

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: 2019030120190301
Explanation:
The first event occurs at timestamp = 20190101 and after 00 and 11 become friends we have the following friendship groups [0,1], [2], [3], [4], [5]. The second event occurs at timestamp = 20190104 and after 33 and 44 become friends we have the following friendship groups [0,1], [2], [3,4], [5]. The third event occurs at timestamp = 20190107 and after 22 and 33 become friends we have the following friendship groups [0,1], [2,3,4], [5]. The fourth event occurs at timestamp = 20190211 and after 11 and 55 become friends we have the following friendship groups [0,1,5], [2,3,4]. The fifth event occurs at timestamp = 20190224 and as 22 and 44 are already friends anything happens. The sixth event occurs at timestamp = 20190301 and after 00 and 33 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: 33

Constraints:

  • 2≀n≀1002 \leq n \leq 100
  • 1≀1 \leq logs.length ≀104\leq 10^4
  • logs[i].length == 3
  • 0≀timestampi≀1090 \leq \text{timestamp}_ i \leq 10^9
  • 0≀xi,yi≀nβˆ’10 \leq x_i, y_i \leq n - 1
  • xiβ‰ yix_i \neq y_i
  • All the values timestampi\text{timestamp}_ i are unique.
  • All the pairs (xi,yi)(x_i, y_i) occur at most one time in the input.

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 timestampj\text{timestamp}_ j. Then, we'll iterate through friendships from the least to greatest timestampj\text{timestamp}_ j 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 11 is connected to all other nβˆ’1n-1 nodes. If the graph isn't connected after processing all the friendships, we'll return βˆ’1-1.

Let's denote the number of friendships(edges) as MM.

Since checking the connectivity of the graph is O(Nlog⁑N)\mathcal{O}(N\log{N}) and we do this O(M)\mathcal{O}(M) times, this solution runs in O(MNlog⁑N)\mathcal{O}(MN\log{N}).

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 11. This is true as this operation turns 22 disjoint sets into 11 disjoint set without disturbing any other disjoint sets. We initially start with NN components (one for each person) and once we reach one component, we'll return the respective timestamp value. βˆ’1-1 will be returned if we never reach one component.

Time Complexity

Sorting takes O(Mlog⁑M)\mathcal{O}(M\log{M}) and the main algorithm runs in O(Mlog⁑N)\mathcal{O}(M\log{N}). Thus our time complexity is O(Mlog⁑M+Mlog⁑N)\mathcal{O}(M\log{M} + M\log{N}).

Time Complexity: O(Mlog⁑M+Mlog⁑N)\mathcal{O}(M\log{M} + M\log{N})

Bonus: We can also use union by rank mentioned here to improve the time complexity of DSU operations from O(log⁑N)\mathcal{O}(\log{N}) to O(α(N))\mathcal{O}(\alpha(N)).

Space Complexity

Our DSU uses O(N)\mathcal{O}(N) memory.

Space Complexity: O(N)\mathcal{O}(N).

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
πŸ’ͺ
Level Up Your
Algo Skills

Got a question?Β Ask the Teaching AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

←
↑TA πŸ‘¨β€πŸ«