Asked at

The Earliest Moment When Everyone Become Friends

Hard
VerifiedUnion FindSortingGreedy~30 min

You have n people labeled 0..n-1. Each entry in logs is [timestamp, a, b], recording that people a and b became friends at that time. Friendship is mutual and transitive.

Return the earliest timestamp at which every person is connected (directly or through friends), or -1 if it never happens.

The input arrives as a single object { logs, n }.

Examples

in{ logs: [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n: 4 }
out3

After the log at time 3, people 0,1,2,3 all belong to one group.

in{ logs: [[1,0,1]], n: 3 }
out-1

Person 2 never becomes friends with anyone, so return -1.

Constraints

  • 2 ≤ n ≤ 100
  • 1 ≤ logs.length ≤ 10⁴
  • logs[i] = [timestamp, a, b], people labeled 0..n-1
  • All timestamps are distinct within a connecting event but may repeat across logs.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.