Problem Statement
You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [xi, yi, timei] indicates that person xi and person yi have a meeting at timei. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.
Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person xi has the secret at timei, then they will share the secret with person yi, and vice versa.
The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.
Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.
Example 1
Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.
Example 2
Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.
Try here before watching the video.
Video Solution
Java Code
class UnionFind {
private int[] rank;
private int[] parent;
public UnionFind(int n) {
this.parent = new int[n];
this.rank = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if(parent[x] != x) {
parent[x] = find(parent[x]); // doing path compression
}
return parent[x];
}
public void union(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if(parentX != parentY) {
if(rank[parentX] > rank[parentY]) {
parent[parentY] = parentX;
} else if(rank[parentX] < rank[parentY]) {
parent[parentX] = parentY;
} else {
parent[parentY] = parentX;
rank[parentX] += 1;
}
}
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public void reset(int x) {
parent[x] = x;
rank[x] = 0;
}
}
class Solution {
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
UnionFind graph = new UnionFind(n);
graph.union(firstPerson, 0);
Map<Integer, List<int[]>> sameTimeMeetings = new TreeMap<>();
for (int[] meeting : meetings) {
int x = meeting[0], y = meeting[1], t = meeting[2];
if(!sameTimeMeetings.containsKey(t)) {
sameTimeMeetings.put(t, new ArrayList<>());
}
sameTimeMeetings.get(t).add(new int[]{x, y});
}
for (int t : sameTimeMeetings.keySet()) {
// Unite two persons taking part in a meeting
for (int[] meeting : sameTimeMeetings.get(t)) {
int x = meeting[0], y = meeting[1];
graph.union(x, y);
}
// If any one knows the secret, both will be connected to 0.
// If no one knows the secret, then reset both.
for (int[] meeting : sameTimeMeetings.get(t)) {
int x = meeting[0], y = meeting[1];
if (!graph.connected(x, 0)) {
// No need to check for y since x and y were united
graph.reset(x);
graph.reset(y);
}
}
}
// Al those who are connected to 0 will know the secret
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (graph.connected(i, 0)) {
ans.add(i);
}
}
return ans;
}
}
C++ Code
class UnionFind {
private:
vector<int> rank;
vector<int> parent;
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n);
for(int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if(parent[x] != x) {
parent[x] = find(parent[x]); // doing path compression
}
return parent[x];
}
void union_set(int x, int y) {
int parentX = find(x);
int parentY = find(y);
if(parentX != parentY) {
if(rank[parentX] > rank[parentY]) {
parent[parentY] = parentX;
} else if(rank[parentX] < rank[parentY]) {
parent[parentX] = parentY;
} else {
parent[parentY] = parentX;
rank[parentX] += 1;
}
}
}
bool connected(int x, int y) {
return find(x) == find(y);
}
void reset(int x) {
parent[x] = x;
rank[x] = 0;
}
};
class Solution {
public:
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
UnionFind graph(n);
graph.union_set(firstPerson, 0);
map<int, vector<vector<int>>> sameTimeMeetings;
for (const auto& meeting : meetings) {
int x = meeting[0], y = meeting[1], t = meeting[2];
sameTimeMeetings[t].push_back({x, y});
}
for (const auto& [t, meetings] : sameTimeMeetings) {
for (const auto& meeting : meetings) {
int x = meeting[0], y = meeting[1];
graph.union_set(x, y);
}
for (const auto& meeting : meetings) {
int x = meeting[0], y = meeting[1];
if (!graph.connected(x, 0)) {
graph.reset(x);
graph.reset(y);
}
}
}
vector<int> ans;
for (int i = 0; i < n; ++i) {
if (graph.connected(i, 0)) {
ans.push_back(i);
}
}
return ans;
}
};
Python Code
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
parentX = self.find(x)
parentY = self.find(y)
if parentX != parentY:
if self.rank[parentX] > self.rank[parentY]:
self.parent[parentY] = parentX
elif self.rank[parentX] < self.rank[parentY]:
self.parent[parentX] = parentY
else:
self.parent[parentY] = parentX
self.rank[parentX] += 1
def reset(self, x):
self.parent[x] = x
self.rank[x] = 0
class Solution:
def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
graph = UnionFind(n)
graph.union(firstPerson, 0)
sameTimeMeetings = {}
for meeting in meetings:
x, y, t = meeting
sameTimeMeetings.setdefault(t, []).append([x, y])
for t, meetings in sorted(sameTimeMeetings.items()):
for meeting in meetings:
x, y = meeting
graph.union(x, y)
for meeting in meetings:
x, y = meeting
if graph.find(x) != graph.find(0):
graph.reset(x)
graph.reset(y)
return [i for i in range(n) if graph.find(i) == graph.find(0)]
Javascript Code
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
const parentX = this.find(x);
const parentY = this.find(y);
if (parentX !== parentY) {
if (this.rank[parentX] > this.rank[parentY]) {
this.parent[parentY] = parentX;
} else if (this.rank[parentX] < this.rank[parentY]) {
this.parent[parentX] = parentY;
} else {
this.parent[parentY] = parentX;
this.rank[parentX]++;
}
}
}
reset(x) {
this.parent[x] = x;
this.rank[x] = 0;
}
}
var findAllPeople = function(n, meetings, firstPerson) {
const graph = new UnionFind(n);
graph.union(firstPerson, 0);
const sameTimeMeetings = new Map();
for (const meeting of meetings) {
const [x, y, t] = meeting;
sameTimeMeetings.set(t, sameTimeMeetings.get(t) || []);
sameTimeMeetings.get(t).push([x, y]);
}
for (const [t, meetings] of [...sameTimeMeetings.entries()].sort((a, b) => a[0] - b[0])) {
for (const meeting of meetings) {
const [x, y] = meeting;
graph.union(x, y);
}
for (const meeting of meetings) {
const [x, y] = meeting;
if (graph.find(x) !== graph.find(0)) {
graph.reset(x);
graph.reset(y);
}
}
}
const ans = [];
for (let i = 0; i < n; ++i) {
if (graph.find(i) === graph.find(0)) {
ans.push(i);
}
}
return ans;
};
Go Code
type UnionFind struct {
parent []int
rank []int
}
func NewUnionFind(n int) *UnionFind {
uf := &UnionFind{
parent: make([]int, n),
rank: make([]int, n),
}
for i := 0; i < n; i++ {
uf.parent[i] = i
uf.rank[i] = 0
}
return uf
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) {
parentX := uf.Find(x)
parentY := uf.Find(y)
if parentX != parentY {
if uf.rank[parentX] > uf.rank[parentY] {
uf.parent[parentY] = parentX
} else if uf.rank[parentX] < uf.rank[parentY] {
uf.parent[parentX] = parentY
} else {
uf.parent[parentY] = parentX
uf.rank[parentX] += 1
}
}
}
func (uf *UnionFind) Reset(x int) {
uf.parent[x] = x
uf.rank[x] = 0
}
func findAllPeople(n int, meetings [][]int, firstPerson int) []int {
graph := NewUnionFind(n)
graph.Union(firstPerson, 0)
sameTimeMeetings := make(map[int][][]int)
for _, meeting := range meetings {
x, y, t := meeting[0], meeting[1], meeting[2]
sameTimeMeetings[t] = append(sameTimeMeetings[t], []int{x, y})
}
for _, t := range sortedKeys(sameTimeMeetings) {
for _, meeting := range sameTimeMeetings[t] {
x, y := meeting[0], meeting[1]
graph.Union(x, y)
}
for _, meeting := range sameTimeMeetings[t] {
x, y := meeting[0], meeting[1]
if graph.Find(x) != graph.Find(0) {
graph.Reset(x)
graph.Reset(y)
}
}
}
result := []int{}
for i := 0; i < n; i++ {
if graph.Find(i) == graph.Find(0) {
result = append(result, i)
}
}
return result
}
func sortedKeys(m map[int][][]int) []int {
keys := make([]int, 0, len(m))
for k := range m {
keys = append(keys, k)
}
sort.Ints(keys)
return keys
}
Complexity Analysis
Time Complexity: O(M * logM + M + N)
Let's say we have M meetings and N people.
- First, we are creating sorted HashMap which would effectively take O(M * logM), because there can be M different times and hence.
- We are processing N people to create
parentandrankarray in UnionFind implementation which would effectively take O(N). - Then we're iterating over the list of meetings, which would effectively take O(M).
- Hence, overall time complexity would be O(M * logM + M + N).
Space Complexity: O(M + N)
Let's say we have M meetings and N people.
- We are creating
HashMapand storing all the meeting information which would effectively take O(M) space. - Secondly, we are creating
parentandrankarray in UnionFind implementation which would effectively take O(N) space. - Hence, overall space complexity would be O(M + N).