Find Center of Star Graph easy
Description
A graph is a star graph on n nodes if it consists of one center node connected to every other node by a single edge — and no other edges. You’re given the edges of such a graph and must return the center node.
Examples
> Case 1:
Input: edges = [[1, 2], [2, 3], [4, 2]]
Output: 2
> Case 2:
Input: edges = [[1, 2], [5, 1], [1, 3], [1, 4]]
Output: 1Constraints
3 <= n <= 10^5edges.length == n - 1- The graph is guaranteed to be a valid star graph.
The dead-simple intuition
A star graph has exactly one center node that touches every edge. Every other node touches exactly one edge.
So we don’t even need to count degrees — the center appears in every edge. Look at any two edges; the node that appears in both is the center.
edges[0] = [1, 2], edges[1] = [2, 3]
^
shared in both → centerCode
Why O(1)? We didn’t build a graph at all. We didn’t loop over edges. We didn’t allocate a degree array. We looked at the first two edges and found our answer — the problem’s structural guarantee did all the work for us. Read the constraints carefully before reaching for an adjacency list.
The degree-counting approach (for if you missed the shortcut)
If you didn’t notice the two-edge trick, the obvious O(n) approach is to count how many edges touch each node — the one with degree n-1 is the center.
That’s perfectly correct, but takes O(n) time and O(n) space — vs. the trick which is O(1) for both.
Why this lives on Day 9
This problem barely uses graph algorithms — but it forces you to think about degrees and read problem guarantees carefully. Those two habits will pay enormous dividends throughout graph practice.
Analysis
| Approach | Time | Space |
|---|---|---|
| Two-edge trick | O(1) | O(1) |
| Degree counting | O(n) | O(n) |