Find All People With Secret — Solution in Python, Java & C++
Find All People With Secret solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Find All People With Secret is a hard coding problem on sorting, depth-first search and breadth-first search, asked in Amazon, Google and Swiggy interviews.
- Difficulty: Hard
- Topics: Sorting, Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google, Swiggy
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n people labelled 0 … n - 1. Person 0 holds a secret and shares it with firstPerson at time 0.
meetings[i] = [x, y, time] says persons x and y meet at that time. People who meet share the secret immediately, so a person who learns it during a meeting can pass it on in any other meeting happening at the same time. Meetings may happen at the same time, and a person may attend several of them.
Return everyone who ends up knowing the secret, in increasing 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: Person 4 never meets anyone who knows.
Example 2
Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation: Person 2's meeting with 1 happens *before* 1 learns anything.
Example 3
Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Constraints
2 <= n <= 10^51 <= meetings.length <= 10^5meetings[i].length == 30 <= x, y <= n - 1x != y1 <= time <= 10^51 <= firstPerson <= n - 1The answer is returned in increasing order.
Hints for Find All People With Secret
Hint 1
Meetings at the same instant form one group, and the secret can travel freely inside it.
Hint 2
So process the meetings in batches of equal time, using a union-find.
Hint 3
After each batch, anyone in it who is not connected to person 0 must be disconnected again — they learned nothing.
How to solve Find All People With Secret
Sort the meetings by time and process each equal-time batch together. Within a batch, union every pair; afterwards, anyone in the batch not joined to person 0's component is reset to a singleton so a later meeting does not wrongly spread the secret through them.
Approach
- Union person 0 with
firstPerson. - Sort the meetings by time and walk them in equal-time runs.
- Union both attendees of each meeting in the run.
- For each person in the run, if their root is not person 0's root, reset their parent to themselves.
- Finally collect every person sharing person 0's root.
Why it works
The reset is the whole problem: without it, two people who merely met earlier would stay connected, so a secret arriving at one of them later would appear to have reached the other backwards in time. Resetting only the batch's participants is safe because, by induction, every component is either person 0's or a singleton before the batch begins.
Complexity
- Time —
O(m log m + n) - Space —
O(n)
Pitfalls
- Processing meetings one at a time misses the secret hopping between simultaneous meetings.
- Forgetting the reset lets the secret travel backwards in time.
- The output must be sorted; walking the people in order gives that for free.
Reference solution
Python
from typing import List
def findAllPeople(n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def uni(a: int, b: int) -> None:
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
uni(0, firstPerson)
ordered = sorted(meetings, key=lambda m: m[2])
i = 0
while i < len(ordered):
j = i
while j < len(ordered) and ordered[j][2] == ordered[i][2]:
j += 1
people = []
for k in range(i, j):
people.append(ordered[k][0])
people.append(ordered[k][1])
uni(ordered[k][0], ordered[k][1])
root = find(0)
for p in people:
if find(p) != root:
parent[p] = p
i = j
root = find(0)
return [p for p in range(n) if find(p) == root]Java
private static int[] fpParent;
private static int fpFind(int x) {
while (fpParent[x] != x) {
fpParent[x] = fpParent[fpParent[x]];
x = fpParent[x];
}
return x;
}
private static void fpUni(int a, int b) {
int ra = fpFind(a), rb = fpFind(b);
if (ra != rb) fpParent[rb] = ra;
}
public static int[] findAllPeople(int n, int[][] meetings, int firstPerson) {
fpParent = new int[n];
for (int i = 0; i < n; i++) fpParent[i] = i;
fpUni(0, firstPerson);
int[][] sorted = meetings.clone();
Arrays.sort(sorted, (a, b) -> a[2] - b[2]);
int i = 0;
while (i < sorted.length) {
int j = i;
while (j < sorted.length && sorted[j][2] == sorted[i][2]) j++;
List<Integer> people = new ArrayList<>();
for (int k = i; k < j; k++) {
people.add(sorted[k][0]);
people.add(sorted[k][1]);
fpUni(sorted[k][0], sorted[k][1]);
}
int root = fpFind(0);
for (int p : people) {
if (fpFind(p) != root) fpParent[p] = p;
}
i = j;
}
List<Integer> out = new ArrayList<>();
int finalRoot = fpFind(0);
for (int p = 0; p < n; p++) if (fpFind(p) == finalRoot) out.add(p);
int[] res = new int[out.size()];
for (int k = 0; k < res.length; k++) res[k] = out.get(k);
return res;
}C++
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
function<int(int)> find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
auto uni = [&](int a, int b) {
int ra = find(a), rb = find(b);
if (ra != rb) parent[rb] = ra;
};
uni(0, firstPerson);
vector<vector<int>> sorted = meetings;
sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
size_t i = 0;
while (i < sorted.size()) {
size_t j = i;
while (j < sorted.size() && sorted[j][2] == sorted[i][2]) j++;
vector<int> people;
for (size_t k = i; k < j; k++) {
people.push_back(sorted[k][0]);
people.push_back(sorted[k][1]);
uni(sorted[k][0], sorted[k][1]);
}
int root = find(0);
for (int p : people) {
if (find(p) != root) parent[p] = p;
}
i = j;
}
vector<int> out;
int finalRoot = find(0);
for (int p = 0; p < n; p++) if (find(p) == finalRoot) out.push_back(p);
return out;
}JavaScript
var findAllPeople = function(n, meetings, firstPerson) {
var i, k;
var parent = [];
for (i = 0; i < n; i++) parent.push(i);
var find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
var uni = function(a, b) {
var ra = find(a), rb = find(b);
if (ra !== rb) parent[rb] = ra;
};
uni(0, firstPerson);
var sorted = meetings.slice();
sorted.sort(function(a, b) { return a[2] - b[2]; });
i = 0;
while (i < sorted.length) {
var j = i;
while (j < sorted.length && sorted[j][2] === sorted[i][2]) j++;
var people = [];
for (k = i; k < j; k++) {
people.push(sorted[k][0]);
people.push(sorted[k][1]);
uni(sorted[k][0], sorted[k][1]);
}
var root = find(0);
for (k = 0; k < people.length; k++) {
if (find(people[k]) !== root) parent[people[k]] = people[k];
}
i = j;
}
var out = [];
var finalRoot = find(0);
for (var p = 0; p < n; p++) if (find(p) === finalRoot) out.push(p);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 274 sorting problems · the whole catalogue
Learn the technique: Sorting Algorithms · Depth-First Search (DFS)