Find Center of Star Graph
Easy · Graphs · Graph
Problem
An undirected star graph has n nodes labeled 1 to n: one center node is joined to every other node, and there are no other edges, so there are exactly n - 1 edges.
You are given the edge list edges, where edges[i] = [u, v] joins u and v (in either order). Return the label of the center node.
Examples
Input: edges = [[4,2],[2,1],[3,2]] Output: 2
Node 2 appears in every edge.
Input: edges = [[5,1],[1,3],[2,1],[4,1]] Output: 1
All four edges touch node 1.
Input: edges = [[1,3],[2,3]] Output: 3
Three nodes: 3 is shared by both edges.
Constraints
- 3 <= n <= 10^5
- len(edges) == n - 1
- 1 <= u, v <= n and u != v
- The edges always form a valid star graph
Approaches
- Baseline: count degrees — time O(n), space O(n)
Follow-up
The O(1) answer leans entirely on the promise that the input is a star. The use cases drop that promise: one checks whether a list of edges is a star at all, the other finds the busiest node of any graph.
Related problems
Start free on Cariara · Coding problems · System design studio
