What is the time complexity of LeetCode 1101. The Earliest Moment When Everyone Become Friends?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1101. The Earliest Moment When Everyone Become Friends?

The Python solution on this page uses O(n) auxiliary space.

The Earliest Moment When Everyone Become Friends — LeetCode 1101 Python Solution

MediumLeetCode PremiumUnion FindArraySorting

Problem: #1101
Pattern: Union-Find
Reading time: 4 min
Source: leetcode.com

The problem

There are n people in a social group labeled from 0 to n - 1. You are given an array logs where logs[i] = [timestampi, xi, yi] indicates that xi and yi will be friends at the time timestampi.

Example

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].

Python solution

Python

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))
        for t, x, y in sorted(logs):
            if find(x) == find(y):
                continue
            p[find(x)] = find(y)
            n -= 1
            if n == 1:
                return t
        return -1

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1101. The Earliest Moment When Everyone Become Friends is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1101. The Earliest Moment When Everyone Become Friends?: LeetCode 1101. The Earliest Moment When Everyone Become Friends is rated Medium on LeetCode.
What is the time complexity of LeetCode 1101. The Earliest Moment When Everyone Become Friends?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1101. The Earliest Moment When Everyone Become Friends?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1101. The Earliest Moment When Everyone Become Friends cover?: LeetCode 1101. The Earliest Moment When Everyone Become Friends is tagged Union Find, Array and Sorting on LeetCode.
Is LeetCode 1101. The Earliest Moment When Everyone Become Friends a premium problem?: Yes. LeetCode 1101. The Earliest Moment When Everyone Become Friends is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.