676. Hub of the Star
A small broadcast network is shaped like a star: one hub machine is cabled directly to every other machine, and there are no other cables. The machines are labelled 1 to n. The array edges lists the n - 1 cables, each as a pair [x, y] of the two machines it joins, in no particular order and with either end written first.
Return the label of the hub. The input is always a valid star with at least three machines, so exactly one machine appears in every cable. You do not need to scan the whole list: the answer can be found in O(1) time and O(1) space by looking at a constant number of cables.
Example 1
- Input:
- edges = [[5,3],[3,1],[2,3],[3,4]]
- Output:
- 3
- Explanation:
Machine 3 appears in every cable, so it is the hub.
Example 2
- Input:
- edges = [[2,6],[4,6],[6,1],[5,6],[3,6]]
- Output:
- 6
- Explanation:
Machine 6 is joined to all of the other five machines.
Constraints
3 ≤ n ≤ 100000
edges.length == n - 1 and every input is a valid star graph
1 ≤ x, y ≤ n, x ≠ y
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(1)
- Space
- O(1)