Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1101.html

1101. The Earliest Moment When Everyone Become Friends

Level

Medium

Description

In a social group, there are N people, with unique integer ids from 0 to N-1.

We have a list of logs, where each logs[i] = [timestamp, id_A, id_B] contains a non-negative integer timestamp, and the ids of two different people.

Each log represents the time in which two different people became friends. Friendship is symmetric: if A is friends with B, then B is friends with A.

Let’s say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B.

Return the earliest time for which every person became acquainted with every other person. Return -1 if there is no such earliest time.

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: 20190301

Explanation:

The first event occurs at timestamp = 20190101 and after 0 and 1 become friends we have the following friendship groups [0,1], [2], [3], [4], [5].

The second event occurs at timestamp = 20190104 and after 3 and 4 become friends we have the following friendship groups [0,1], [2], [3,4], [5].

The third event occurs at timestamp = 20190107 and after 2 and 3 become friends we have the following friendship groups [0,1], [2,3,4], [5].

The fourth event occurs at timestamp = 20190211 and after 1 and 5 become friends we have the following friendship groups [0,1,5], [2,3,4].

The fifth event occurs at timestamp = 20190224 and as 2 and 4 are already friend anything happens.

The sixth event occurs at timestamp = 20190301 and after 0 and 3 become friends we have that all become friends.

Note:

  1. 2 <= N <= 100
  2. 1 <= logs.length <= 10^4
  3. 0 <= logs[i][0] <= 10^9
  4. 0 <= logs[i][1], logs[i][2] <= N - 1
  5. It’s guaranteed that all timestamps in logs[i][0] are different.
  6. logs are not necessarily ordered by some criteria.
  7. logs[i][1] != logs[i][2]

Solution

First sort logs according to timestamps in ascending order. Then use to maps to store each person and the group that the person belongs to, and each group and the set of people of the group. Initially, each person belongs to the own group, and each group’s set contains only one person.

Loop over logs. If for one log, the two people belong to different groups, then merge the people of the two groups into one group, updating both maps. For the map that stores each group and the set of the people of the group, remove the one group that is obsoleted from the set. Once the latter map’s size becomes 1, everyone becomes friends, so return the timestamp.

If the latter map’s size is always greater than 1, then there is no such time that everyone becomes friends, so return -1.

  • class Solution {
    public int earliestAcq(int[][] logs, int N) {
        Arrays.sort(logs, new Comparator<int[]>() {
            public int compare(int[] log1, int[] log2) {
                return log1[0] - log2[0];
            }
        });
        Map<Integer, Integer> personGroupMap = new HashMap<Integer, Integer>();
        Map<Integer, Set<Integer>> groupSetMap = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < N; i++) {
            personGroupMap.put(i, i);
            Set<Integer> set = new HashSet<Integer>();
            set.add(i);
            groupSetMap.put(i, set);
        }
        int length = logs.length;
        for (int i = 0; i < length; i++) {
            int[] log = logs[i];
            int timestamp = log[0], person1 = log[1], person2 = log[2];
            if (person1 > person2) {
                int temp = person1;
                person1 = person2;
                person2 = temp;
            }
            int group1 = personGroupMap.get(person1), group2 = personGroupMap.get(person2);
            if (group1 != group2) {
                Set<Integer> set1 = groupSetMap.get(group1);
                Set<Integer> set2 = groupSetMap.get(group2);
                if (group1 < group2) {
                    set1.addAll(set2);
                    for (int person : set1)
                        personGroupMap.put(person, group1);
                    groupSetMap.put(group1, set1);
                    groupSetMap.remove(group2);
                } else {
                    set2.addAll(set1);
                    for (int person : set2)
                        personGroupMap.put(person, group2);
                    groupSetMap.put(group2, set2);
                    groupSetMap.remove(group1);
                }
                if (groupSetMap.size() == 1)
                    return timestamp;
            }
        }
        return -1;
    }
}

  • // OJ: https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/
// Time: O(NlogN)
// Space: O(N)
class UnionFind {
    vector<int> id;
    int cnt;
public:
    UnionFind(int n) : id(n), cnt(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int x = find(a), y = find(b);
        if (x == y) return;
        id[x] = y;
        --cnt;
    }
    int getCount() { return cnt; }
};
class Solution {
public:
    int earliestAcq(vector<vector<int>>& A, int n) {
        sort(begin(A), end(A));
        UnionFind uf(n);
        for (auto &log : A) {
            int t = log[0], u = log[1], v = log[2];
            uf.connect(u, v);
            if (uf.getCount() == 1) return t;
        }
        return -1;
    }
};

  • class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        logs.sort()
        for t, a, b in logs:
            if find(a) == find(b):
                continue
            p[find(a)] = find(b)
            n -= 1
            if n == 1:
                return t
        return -1



  • func earliestAcq(logs [][]int, n int) int {
	sort.Slice(logs, func(i, j int) bool { return logs[i][0] < logs[j][0] })
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, log := range logs {
		t, x, y := log[0], log[1], log[2]
		if find(x) == find(y) {
			continue
		}
		p[find(x)] = find(y)
		n--
		if n == 1 {
			return t
		}
	}
	return -1
}

All Problems

All Solutions