How do you solve Find All People With Secret on LeetCode?

Find All People With Secret (LeetCode #2092) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using union-find helps efficiently manage groups of people sharing secrets.

What is the brute force solution for Find All People With Secret?

The brute force approach for Find All People With Secret is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we simulate each meeting and check who knows the secret at each time. We iterate through all meetings and update the knowledge of the secret based on the current attendees. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Find All People With Secret?

Explain your thought process clearly; it shows your understanding. Consider edge cases, such as when there are no meetings or only one person. Practice union-find problems to get comfortable with the data structure.

What are common mistakes when solving Find All People With Secret?

Not sorting the meetings by time before processing. Forgetting to check if both participants of a meeting know the secret.

#2092

Find All People With Secret

Hard

Depth-First SearchBreadth-First SearchUnion-FindGraph TheorySortingUnion-FindGraph Theory

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

This approach uses a graph representation of the meetings and a union-find data structure to efficiently manage the sharing of secrets. We process meetings in chronological order and use union operations to group people who can share the secret.

⚙️

Algorithm

3 steps

1Step 1: Sort the meetings by time.
2Step 2: Use a union-find structure to group people who meet at the same time.
3Step 3: After processing all meetings, check which groups contain people who know the secret and return them.

solution.py25 lines

1class UnionFind:
2    def __init__(self, size):
3        self.parent = list(range(size))
4    def find(self, x):
5        if self.parent[x] != x:
6            self.parent[x] = self.find(self.parent[x])
7        return self.parent[x]
8    def union(self, x, y):
9        rootX = self.find(x)
10        rootY = self.find(y)
11        if rootX != rootY:
12            self.parent[rootY] = rootX
13
14
15def findAllPeople(n, meetings, firstPerson):
16    uf = UnionFind(n)
17    meetings.sort(key=lambda x: x[2])
18    meetings.append([0, 0, 0])  # Add a dummy meeting for union-find
19    for x, y, time in meetings:
20        uf.union(x, y)
21    secret_holders = set()
22    for i in range(n):
23        if uf.find(i) == uf.find(0) or uf.find(i) == uf.find(firstPerson):
24            secret_holders.add(i)
25    return list(secret_holders)

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the meetings, while the union-find operations are nearly constant time, making this approach efficient.

1Using union-find helps efficiently manage groups of people sharing secrets.
2Processing meetings in chronological order ensures that secrets are shared as soon as possible.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.