When did everyone first connect?
Watch the group count drop as merges happen, and note the moment it reaches 1. About 10 minutes.
Watch the count as you go
You already know how to count groups at the end. This time the question is when: after which merge does everyone first end up in one group?
So keep the count running and check it after every single cable, not just at the end. And think about what to return if it never gets there.
- edge
- 0
- groups
- 4
Keep a running group count and check it after every edge.
3 people, cables 0-1, then 0-1 again, then 1-2. After which cable is everyone first connected?
- AThe 3rd
- BThe 2nd
Show the answer
The 3rd. The first cable leaves 2 groups, the second changes nothing, and the third joins the last person in.
When did everyone first connect?
There are n people, numbered 0 to n - 1, each starting alone. edges lists pairs [a, b] processed in order, merging groups when they're not already merged. Return the 1-based position in edges of the merge after which every person first belongs to one single group, or -1 if that never happens.
n = 3, edges = [[0, 1], [0, 1], [1, 2]] → 3
1 ≤ n ≤ 100,000 · 0 ≤ edges.length ≤ 100,000 · edges[i] has two different node numbers, each 0 ≤ x < n