Earliest Time a Friendship Network Is Fully Connected with Friend and Unfriend Events
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
There are `n` people in a social network, labeled `0` to `n - 1`. You are given a log of friendship events, `logs`, where `logs[i] = [timestamp, a, b, action]` means that at time `timestamp`, people `a` and `b` become friends if `action` is `1`, or stop being friends (unfriend) if `action` is `0`. Friendship is symmetric.
Two people are acquainted if they are friends, or if one can reach the other through a chain of people who are friends at that moment. The network is fully connected when every pair of people is acquainted.
Return the earliest timestamp at which the network is fully connected, or `-1` if that never happens.
### Function Signature
```python
def earliest_full_connection(n: int, logs: list[list[int]]) -> int:
```
### Rules
- Before the first event, nobody is friends with anybody.
- The log is not necessarily sorted. Events take effect in increasing order of `timestamp`, and no two events share a timestamp.
- The network at time `t` is the result of applying every event whose timestamp is at most `t`. The answer is the timestamp of the first event after which the network is fully connected.
- An event with `action = 1` always names two people who are not friends at that moment, and an event with `action = 0` always names two people who are friends at that moment.
- A network that is fully connected at some time may be split again by later unfriend events; that does not change the answer, which is the first time the network is fully connected.
### Constraints
- `2 <= n <= 1000`
- `1 <= len(logs) <= 2000`
- `logs[i]` has exactly four integers: `0 <= timestamp <= 10^9`, `0 <= a < n`, `0 <= b < n`, `a != b`, and `action` is `0` or `1`.
- All timestamps are distinct.
- The events satisfy the validity rule above when applied in timestamp order.
- The answer is either `-1` or one of the timestamps in `logs`, so it is uniquely determined by the input.
### Examples
**Example 1**
- Input: `n = 4`, `logs = [[3, 0, 1, 1], [7, 2, 3, 1], [1, 1, 2, 1], [9, 0, 3, 1]]`
- Output: `7`
- Explanation: In time order: at 1, people 1 and 2 become friends; at 3, people 0 and 1 do, giving the group {0, 1, 2} and person 3 alone; at 7, people 2 and 3 become friends, which connects everyone. The event at 9 comes later and does not matter.
**Example 2**
- Input: `n = 4`, `logs = [[5, 2, 3, 1], [6, 1, 3, 1], [1, 0, 1, 1], [2, 1, 2, 1], [4, 1, 2, 0]]`
- Output: `6`
- Explanation: In time order: at 1 and 2, the group {0, 1, 2} forms; at 4, people 1 and 2 unfriend, leaving {0, 1} and {2}; at 5, people 2 and 3 become friends, giving {0, 1} and {2, 3}; at 6, people 1 and 3 become friends, which connects everyone. Without the unfriend event at 4, the answer would have been 5.
**Example 3**
- Input: `n = 3`, `logs = [[1, 0, 1, 1], [2, 0, 1, 0], [3, 1, 2, 1]]`
- Output: `-1`
- Explanation: At 1, only people 0 and 1 are friends and person 2 is alone; at 2, they unfriend and nobody is friends; at 3, people 1 and 2 become friends and person 0 is alone. The network is never fully connected.
Overview: Given an unsorted log of timestamped friend and unfriend events among n people, return the earliest time at which everyone is connected through chains of friendships, or -1 if that never happens. It tests connectivity reasoning when edges can be both added and removed, event ordering, and careful handling of groups that split apart again.
There are `n` people in a social network, labeled `0` to `n - 1`. You are given a log of friendship events, `logs`, where `logs[i] = [timestamp, a, b, action]` means that at time `timestamp`, people `a` and `b` become friends if `action` is `1`, or stop being friends if `action` is `0`. Friendship is symmetric.
Two people are **acquainted** if they are friends, or if one can reach the other through a chain of people who are friends at that moment. The network is **fully connected** when every pair of people is acquainted.
Return the earliest timestamp at which the network is fully connected, or `-1` if that never happens.
### Rules
- Before the first event, nobody is friends with anybody.
- The log is **not necessarily sorted**. Events take effect in increasing order of `timestamp`, and no two events share a timestamp.
- The network at time `t` is the result of applying every event whose timestamp is at most `t`. The answer is the timestamp of the first event after which the network is fully connected.
- An event with `action = 1` always names two people who are not friends at that moment, and an event with `action = 0` always names two people who are friends at that moment.
- A network that is fully connected at some time may be split again by later unfriend events. That does not change the answer, which is the **first** time the network is fully connected.
### Output
Return a single integer: the timestamp of the first event after which all `n` people are acquainted, or `-1` if no such event exists. Because all timestamps are distinct, this value is uniquely determined by the input. Every timestamp and the answer fit in a signed 32-bit integer.
### Constraints
- `2 <= n <= 1000`
- `1 <= len(logs) <= 2000`
- `logs[i]` has exactly four integers: `0 <= timestamp <= 10^9`, `0 <= a < n`, `0 <= b < n`, `a != b`, and `action` is `0` or `1`.
- All timestamps are distinct.
- The events satisfy the rules above when applied in timestamp order.
### Example 1
- Input: `n = 4`, `logs = [[3, 0, 1, 1], [7, 2, 3, 1], [1, 1, 2, 1], [9, 0, 3, 1]]`
- Output: `7`
- Explanation: In time order: at 1, people 1 and 2 become friends; at 3, people 0 and 1 do, giving the group {0, 1, 2} with person 3 alone; at 7, people 2 and 3 become friends, which connects everyone. The event at 9 comes later and does not matter.
### Example 2
- Input: `n = 4`, `logs = [[5, 2, 3, 1], [6, 1, 3, 1], [1, 0, 1, 1], [2, 1, 2, 1], [4, 1, 2, 0]]`
- Output: `6`
- Explanation: At 1 and 2 the group {0, 1, 2} forms; at 4, people 1 and 2 unfriend, leaving {0, 1} and {2}; at 5, people 2 and 3 become friends, giving {0, 1} and {2, 3}; at 6, people 1 and 3 become friends, which connects everyone. Without the unfriend event at 4, the answer would have been 5.
### Example 3
- Input: `n = 3`, `logs = [[1, 0, 1, 1], [2, 0, 1, 0], [3, 1, 2, 1]]`
- Output: `-1`
- Explanation: At no moment are all three people acquainted.
Constraints
- 2 <= n <= 1000
- 1 <= len(logs) <= 2000
- logs[i] = [timestamp, a, b, action] has exactly four integers
- 0 <= timestamp <= 10^9 (fits in a signed 32-bit integer)
- 0 <= a < n, 0 <= b < n, a != b
- action is 0 (unfriend) or 1 (befriend)
- All timestamps are distinct; logs is not necessarily sorted
- Applied in timestamp order, every befriend event names two people who are not friends and every unfriend event names two people who are friends
Examples
Input: (4, [[3, 0, 1, 1], [7, 2, 3, 1], [1, 1, 2, 1], [9, 0, 3, 1]])
Expected Output: 7
Explanation: Example 1: in time order the groups merge at 1 and 3, and the event at 7 joins person 3.
Input: (4, [[5, 2, 3, 1], [6, 1, 3, 1], [1, 0, 1, 1], [2, 1, 2, 1], [4, 1, 2, 0]])
Expected Output: 6
Explanation: Example 2: the unfriend at 4 splits {0, 1, 2}, so the network first connects at 6, not 5.
Hints
- The order of the list is not the order of time. What should happen to the events before you replay them?
- Unfriend events can split a group, so a structure that only ever merges groups is not enough on its own. With at most 1000 people and 2000 events, a full graph traversal after an event is affordable.
- Removing a friendship can never make the network more connected, and n people need at least n - 1 friendships to be connected. When is it actually worth checking?
Community answers
Answer by Coderka14
#include
using namespace std;
class DSU {
vector parent, sz;
public:
DSU(int n) {
parent.resize(n);
sz.assign(n, 1);
for (int i = 0; i < n; i++)
parent[i] = i;
}
int find(int x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return false;
if (sz[a] < sz[b])
swap(a, b);
parent[b] = a;
sz[a] += sz[b];
return true;
}
};
class Solution {
public:
int earliest_full_connection(int n, vector>& logs) {
sort(logs.begin(), logs.end());
set> edges;
for (auto& log : logs) {
int time = log[0];
int a = log[1];
int b = log[2];
int action = log[3];
if (a > b)
swap(a, b);
if (action == 0) {
// Unfriend: just remove the edge.
edges.erase({a, b});
continue;
}
// Friend: add the new edge.
edges.insert({a, b});
// Rebuild DSU using current active edges.
DSU dsu(n);
int components = n;
for (auto& edge : edges) {
if (dsu.unite(edge.first, edge.second))
components--;
}
if (components == 1)
return time;
}
return -1;
}
};