Skip to main content
Talentd

Find All People With Secret - Solution & Explanation

HardDepth-First SearchBreadth-First SearchUnion FindGraph20 min readAsked at: Amazon, Uber, Google
Practice this problem

Problem Statement

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. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person xi has the secret at timei, then they will share the secret with person yi, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

 

Example 1:

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.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.​​​​
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2:

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3:

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

 

Constraints:

  • 2 <= n <= 105
  • 1 <= meetings.length <= 105
  • meetings[i].length == 3
  • 0 <= xi, yi <= n - 1
  • xi != yi
  • 1 <= timei <= 105
  • 1 <= firstPerson <= n - 1

Approach Overview

Problem Overview: You have n people and a list of meetings [x, y, time]. Person 0 initially knows a secret and shares it with firstPerson. Whenever two people meet, the secret spreads instantly if either participant already knows it. The challenge is handling meetings that occur at the same time while ensuring the secret only spreads through valid chains.

Approach 1: Union-Find with Time Reset (Sorting + Disjoint Set) (Time: O(m log m), Space: O(n))

Sort all meetings by time so you process them chronologically. For meetings occurring at the same timestamp, temporarily connect participants using a Union-Find structure. If a connected component contains someone who already knows the secret (initially person 0 and firstPerson), the secret propagates to the entire component. After finishing a time block, reset connections for groups that are not connected to the secret holder so the secret cannot incorrectly travel to later meetings. This works because meetings at the same time form temporary communication networks that should not persist beyond that timestamp.

This approach relies heavily on the Union Find data structure for near-constant connectivity checks. Sorting ensures chronological correctness. Path compression and union by rank keep operations efficient even when the number of meetings is large.

Approach 2: Graph Traversal Per Time Block (BFS/DFS) (Time: O(m log m + m), Space: O(m))

Another way to model the problem is as a series of small graphs formed by meetings that occur at the same time. Start by sorting meetings by time. For each timestamp, build an adjacency list connecting everyone who meets during that moment. Then run a traversal (either BFS or DFS) starting from participants who already know the secret. Anyone reachable within that time-block graph learns the secret as well.

After finishing traversal for that timestamp, discard the graph and move to the next time group. This prevents information from leaking through edges that should only exist temporarily. The traversal naturally fits standard Breadth-First Search or Depth-First Search patterns used in graph problems.

Recommended for interviews: The Union-Find approach is usually the expected optimal solution because it handles dynamic connectivity efficiently and demonstrates strong understanding of disjoint-set structures. Graph traversal per time block is also valid and often easier to reason about during implementation. Interviewers typically want to see that you first recognize the need to process meetings in chronological order, then model simultaneous meetings as temporary connectivity groups.

Approach 1: Union-Find Approach

We sort the meetings by time and use the Union-Find (Disjoint Set) data structure to manage which groups of people know the secret at each point in time. Initially, person 0 knows the secret and shares it with the firstPerson at time 0. As the meetings progress, we perform union operations on people involved in meetings at the same time, and for each new time, we propagate the secret within the connected components.

We first sort the meetings by their time. For each group of meetings happening at the same time, we union the respective people and then check if any of them know the secret. If they do, we propagate the knowledge to everyone in the same connected component (group of people who can share the secret due to the meetings). Finally, we reset the connected components and check who knows the secret by the end of all meetings.

Code

PythonC++

Python

C++

Complexity

The time complexity is O((n + m) log m) where n is the number of people and m is the number of meetings. This accounts for sorting the meetings and performing union-find operations. The space complexity is O(n) due to the storage required for parent tracking and knowledge status.

Try this approach in the editor →

Approach 2: Graph Traversal (BFS/DFS) Approach

We can view the people and their meetings as a graph where people are nodes and meetings are edges with timestamps. We perform Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the graph, starting from person 0 and the initially known first person, propagating secret knowledge among connected nodes (people) within allowable time frames.

In this approach, we first sort the meetings by time, then use a BFS to traverse starting from person 0 and the firstPerson. As we go through the sorted meetings, we use a queue to track who currently knows the secret. If a person is in a meeting pair with someone else who knows the secret, they learn it too. We keep propagating this knowledge as we traverse.

Code

JavaJavaScript

Java

JavaScript

Complexity

The time complexity here is O(m log m + m) due to sorting and BFS traversal, where m is the number of meetings. Space complexity is O(n + m) to hold our data structures for tracking secret knowledge.

Try this approach in the editor →

Approach 3: Simulation + Graph Traversal

The core idea of this problem is to find all people who eventually know the secret by simulating the propagation process through meetings. We can treat each meeting as an edge in an undirected graph, where each participant is a node in the graph, and the meeting time is the "timestamp" of the edge connecting the nodes. At each time point, we traverse all meetings and use Breadth-First Search (BFS) to simulate the propagation of the secret.

We create a boolean array vis to record whether each person knows the secret. Initially, vis[0] = true and vis[firstPerson] = true, indicating that person 0 and firstPerson already know the secret.

We first sort the meetings by time to ensure that we process meetings in the correct order during each traversal.

Next, we process each group of meetings at the same time. For each group of meetings at the same time (i.e., meetings[i][2] = meetings[i+1][2]), we treat them as events occurring at the same moment. For each meeting, we record the relationships between participants and add these participants to a set.

Then, we use BFS to propagate the secret. For all participants at the current time point, if any of them already know the secret, we will traverse the adjacent nodes of that participant (i.e., other participants in the meeting) through BFS and mark them as knowing the secret. This process continues to propagate until all people who can know the secret at this meeting are updated.

When all meetings are processed, we traverse the vis array, add the IDs of all people who know the secret to the result list, and return it.

The time complexity is O(m times log m + n), and the space complexity is O(n), where m and n are the number of meetings and the number of experts, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Union-Find Approach

The time complexity is O((n + m) log m) where n is the number of people and m is the number of meetings. This accounts for sorting the meetings and performing union-find operations. The space complexity is O(n) due to the storage required for parent tracking and knowledge status.

Graph Traversal (BFS/DFS) Approach

The time complexity here is O(m log m + m) due to sorting and BFS traversal, where m is the number of meetings. Space complexity is O(n + m) to hold our data structures for tracking secret knowledge.

Simulation + Graph Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Union-Find with Time ResetO(m log m)O(n)Best general solution for interviews. Efficient connectivity tracking when meetings occur in time batches.
Graph Traversal per Time Block (BFS/DFS)O(m log m + m)O(m)Useful when you prefer explicit graph modeling and traversal logic for each timestamp.

Video Solution

Find All People With Secret | 4 Approaches | Google | Leetcode 2092 | codestorywithMIK • codestorywithMIK • 12,840 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find All People With Secret easy or hard?
Find All People With Secret is labeled Hard because it combines multiple concepts: sorting by time, dynamic connectivity, and graph traversal. The tricky part is handling meetings that happen at the same timestamp without letting connections persist incorrectly.
Find All People With Secret Python/Java solution
Python and C++ implementations commonly use the Union-Find approach with path compression. Java and JavaScript solutions often model meetings as graphs per timestamp and run BFS or DFS to spread the secret. Both strategies achieve roughly O(m log m) time complexity.
How to solve Find All People With Secret in O(m log m)?
First sort all meetings by their time value. Process meetings in groups with the same timestamp and connect participants using Union-Find or build a temporary graph. If any person in that group already knows the secret, propagate it to all reachable members. Sorting plus near-constant connectivity operations leads to O(m log m) complexity.
What is the best approach for Find All People With Secret?
The most common optimal approach uses Union-Find after sorting meetings by time. For each timestamp, temporarily union participants and check whether their component connects to someone who already knows the secret. Components not connected to the secret are reset before moving to the next time group. This results in O(m log m) time due to sorting.
Is Find All People With Secret asked at Google/Amazon/Meta?
Problems involving Union-Find, time-based event processing, and graph connectivity appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of dynamic connectivity and graph traversal under constraints.
What data structure is used in Find All People With Secret?
The main data structures are Union-Find (Disjoint Set Union) for dynamic connectivity and adjacency lists for graph traversal. Sorting is also required to process meetings chronologically. Together these structures efficiently model temporary communication networks formed by simultaneous meetings.
What is the time complexity of Find All People With Secret?
The optimal time complexity is O(m log m), where m is the number of meetings. Sorting the meetings by timestamp dominates the runtime, while Union-Find operations run in near O(1) amortized time with path compression. Space complexity is O(n) for storing parent relationships.

Ready to solve this problem?

Practice Find All People With Secret with our built-in code editor and test cases.

Practice on FleetCode
Previous

Reachable Nodes In Subdivided Graph