Leetcode 1101 The Earliest Moment When Everyone Become Friends

Problem statement

https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

Solution

This is classical union find problem, where we need to traverse our graph and add edge by edge. If we have one component with all elements, return this time.

Complexity

Time complexity is O(N log N + M), where M = len(logs). Space complexity is O(N).

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def earliestAcq(self, logs, N):
        dsu = DSU(N)
        comps = N
        for time, x, y in sorted(logs):
            if dsu.find(x) != dsu.find(y):
                comps -= 1
                dsu.union(x, y)

            if comps == 1: return time

        return -1