Find All People With Secret - Practice Coding Problems

Find All People With Secret - Problem

Imagine you're tracking the spread of confidential information through a network of meetings! 🕵️

You have n people numbered from 0 to n-1. Person 0 knows a secret and initially shares it with firstPerson at time 0.

You're given an array meetings where meetings[i] = [xi, yi, timei] means person xi and person yi meet at time timei. When someone who knows the secret meets someone else, they instantly share the secret!

Key insight: If multiple meetings happen at the same time, the secret can spread through all connected people in that time frame before moving to the next time.

Goal: Return all people who know the secret after all meetings are complete.

Input & Output

example_1.py — Basic Secret Spreading

$ Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1

› Output: [0, 1, 2, 3]

💡 Note: Person 0 tells person 1 initially. At time 5, person 1 meets person 2 and shares the secret. At time 8, person 2 meets person 3 and shares the secret. Person 5 meets person 1 at time 10 but person 5 doesn't initially know the secret, so they learn it then.

example_2.py — Simultaneous Meetings

$ Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3

› Output: [0, 1, 3]

💡 Note: Person 0 tells person 3 initially. At time 2, person 1 meets person 2, but neither knows the secret. At time 3, person 3 meets person 1 (learning the secret) and person 0 meets person 3 simultaneously. This creates a connected component where the secret spreads to person 1.

example_3.py — No Additional Spread

$ Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1

› Output: [0, 1, 2, 3]

💡 Note: Person 0 tells person 1 initially. At time 1, persons 1-2 meet and 2-3 meet simultaneously, so the secret spreads to persons 2 and 3. At time 2, persons 3-4 meet, so person 4 learns the secret. Person 4 is not connected to anyone with the secret at this point.

Constraints

2 ≤ n ≤ 10⁵
0 ≤ meetings.length ≤ 10⁵
meetings[i].length == 3
0 ≤ xi, yi ≤ n - 1
xi ≠ yi
1 ≤ timei ≤ 10⁵
1 ≤ firstPerson ≤ n - 1
Each meeting involves exactly two distinct people

Visualization

Tap to expand

Understanding the Visualization

Initial State

Person 0 and firstPerson know the secret

Time-based Processing

Group meetings by timestamp and process chronologically

Component Formation

Use Union-Find to connect people meeting at same time

Secret Propagation

Spread secret through entire connected components

Final Result

All people who learned the secret through the network

Key Takeaway

🎯 Key Insight: Use Union-Find to efficiently group people meeting simultaneously, then propagate secrets through entire connected components at once. This handles the instantaneous spreading requirement optimally.

Asked in

G Google 45 f Meta 38 a Amazon 32 ⊞ Microsoft 28

This problem requires tracking secret propagation through a meeting network. The optimal approach uses Union-Find to group people who meet at the same time into connected components, then spreads the secret through entire components at once. Key insight: process meetings chronologically and handle simultaneous meetings as connected graphs where the secret spreads instantly through all connected people.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Simulation)	O(m² * n)	O(n)	Simulate each meeting individually and track secret spread
Union-Find (Optimal)	O(m log m + m * α(n))	O(n + m)	Group people by time using Union-Find, then propagate secrets through connected components

Brute Force (Simulation) — Algorithm Steps

Sort all meetings by time
Initialize a set with people who know the secret (0 and firstPerson)
For each meeting, check if either person knows the secret
If so, add the other person to the secret holders
Repeat until no more changes occur at each time step

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort meetings

Arrange all meetings in chronological order

Group by time

Collect meetings happening at same time

Iterate until stable

Keep spreading secret until no new people learn it

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    int* meetingA = *(int**)a;
    int* meetingB = *(int**)b;
    return meetingA[2] - meetingB[2];
}

int* findAllPeople(int n, int** meetings, int meetingsSize, int* meetingsColSize, int firstPerson, int* returnSize) {
    // Sort meetings by time
    qsort(meetings, meetingsSize, sizeof(int*), compare);
    
    bool* knowsSecret = (bool*)calloc(n, sizeof(bool));
    knowsSecret[0] = true;
    knowsSecret[firstPerson] = true;
    
    int i = 0;
    while (i < meetingsSize) {
        int currentTime = meetings[i][2];
        
        // Process all meetings at current time
        int start = i;
        while (i < meetingsSize && meetings[i][2] == currentTime) {
            i++;
        }
        
        bool changed = true;
        while (changed) {
            changed = false;
            for (int j = start; j < i; j++) {
                int x = meetings[j][0], y = meetings[j][1];
                if (knowsSecret[x] && !knowsSecret[y]) {
                    knowsSecret[y] = true;
                    changed = true;
                } else if (knowsSecret[y] && !knowsSecret[x]) {
                    knowsSecret[x] = true;
                    changed = true;
                }
            }
        }
    }
    
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = 0;
    for (int i = 0; i < n; i++) {
        if (knowsSecret[i]) {
            result[(*returnSize)++] = i;
        }
    }
    
    free(knowsSecret);
    return result;
}

int main() {
    // Parse input and call solution
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m² * n)

May need to iterate through meetings multiple times until convergence, where m is meetings and n is people

✓ Linear Growth

Space Complexity

O(n)

Space for tracking who knows the secret

⚡ Linearithmic Space

52.4K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Simulation) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler