FastPrepFind All People With the Secret
Problem · Graph

Find All People With the Secret

Learn this problem
● HardGoogle logoGoogleNEW GRADPHONE SCREEN
See Google hiring insights

Problem statement

There are n people numbered from 0 to n - 1. Initially, person 0 shares a secret with firstPerson at time 0.

Each meeting is [x, y, time]. If either participant knows the secret at that time, both know it after the meeting. All meetings with the same timestamp happen simultaneously: knowledge may travel through an entire connected component formed by meetings at that timestamp, but it must not leak to a component that had no informed member when that timestamp began.

Return every person who knows the secret after all meetings, in ascending order.

Function

findAllPeople(n: int, meetings: int[][], firstPerson: int) → int[]

Examples

Example 1

n = 6meetings = [[1,2,5],[2,3,8],[1,5,10]]firstPerson = 1return = [0,1,2,3,5]

People 0 and 1 start informed. Person 2 learns at time 5, person 3 at time 8, and person 5 at time 10.

Example 2

n = 6meetings = [[1,2,5],[2,3,5],[4,5,5]]firstPerson = 1return = [0,1,2,3]

At time 5, the informed person 1 spreads the secret through the simultaneous chain 1-2-3. The separate component 4-5 remains uninformed.

Constraints

  • 2 <= n <= 100000
  • 1 <= meetings.length <= 100000
  • Every meeting is [x, y, time] with 0 <= x, y < n, x != y, and 1 <= time <= 1000000000.
  • 1 <= firstPerson < n.
  • Duplicate meetings are allowed.

More Google problems

drafts saved locally
public int[] findAllPeople(int n, int[][] meetings, int firstPerson) {
    // Write your code here.
}
n6
meetings[[1,2,5],[2,3,8],[1,5,10]]
firstPerson1
expected[0,1,2,3,5]
checking account