How hard is LeetCode 2092. Find All People With Secret?

LeetCode 2092. Find All People With Secret is rated Hard on LeetCode.

What is the time complexity of LeetCode 2092. Find All People With Secret?

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

What is the space complexity of LeetCode 2092. Find All People With Secret?

The Python solution on this page uses O(n), where m and n are the number of meetings and the number of experts, respectively auxiliary space.

What topics does LeetCode 2092. Find All People With Secret cover?

LeetCode 2092. Find All People With Secret is tagged Depth-First Search, Breadth-First Search, Union Find, Graph and Sorting on LeetCode.

Find All People With Secret — LeetCode 2092 Python Solution

HardDepth-First SearchBreadth-First SearchUnion FindGraphSorting

Problem: #2092
Pattern: Union-Find
Reading time: 5 min
Source: leetcode.com

The problem

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.

Example

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.

Python solution

Python

class Solution:
    def findAllPeople(
        self, n: int, meetings: List[List[int]], firstPerson: int
    ) -> List[int]:
        vis = [False] * n
        vis[0] = vis[firstPerson] = True
        meetings.sort(key=lambda x: x[2])
        i, m = 0, len(meetings)
        while i < m:
            j = i
            while j + 1 < m and meetings[j + 1][2] == meetings[i][2]:
                j += 1
            s = set()
            g = defaultdict(list)
            for x, y, _ in meetings[i : j + 1]:
                g[x].append(y)
                g[y].append(x)
                s.update([x, y])
            q = deque([u for u in s if vis[u]])
            while q:
                u = q.popleft()
                for v in g[u]:
                    if not vis[v]:
                        vis[v] = True
                        q.append(v)
            i = j + 1
        return [i for i, v in enumerate(vis) if v]

Complexity

Measure	Complexity
Time	O(m \times \log m + n)
Space	O(n), where m and n are the number of meetings and the number of experts, respectively auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2092. Find All People With Secret is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

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 2092. Find All People With Secret?: LeetCode 2092. Find All People With Secret is rated Hard on LeetCode.
What is the time complexity of LeetCode 2092. Find All People With Secret?: The Python solution on this page runs in O(m \times \log m + n).
What is the space complexity of LeetCode 2092. Find All People With Secret?: The Python solution on this page uses O(n), where m and n are the number of meetings and the number of experts, respectively auxiliary space.
What topics does LeetCode 2092. Find All People With Secret cover?: LeetCode 2092. Find All People With Secret is tagged Depth-First Search, Breadth-First Search, Union Find, Graph and Sorting on LeetCode.