Find Center of Star Graph

1. Define the problem

You are given a star graph : one middle node is joined to every other node, and there are no other connections. The graph is given as a list of edges, where each edge is a pair of node numbers that are joined. Return the number of the center node . You do not need to count anything. Look at the first two edges only : the center sits on every edge, so the one node that appears in both of those edges has to be the center.

Constraints

3 ≤ n ≤ 10⁵, where n is the number of nodes
edges.length === n - 1
Node numbers run from 1 to n
The input is guaranteed to be a valid star graph

Example

Inputedges = [[1, 2], [2, 3], [4, 2]]

Output2

Explanation Node 2 appears in all three edges, so every other node is joined only to node 2. Node 2 is the center.

2. Know the words first

In plain terms

Graph: A set of nodes (also called vertices) and the connections between them (called edges). Think of cities joined by roads.
Edge: One connection between two nodes, written here as a pair like [1, 2] meaning node 1 and node 2 are joined.
Star graph: A graph shaped like a star: one node in the middle joined to all the others, and no connections between the outer nodes.
Degree: How many edges touch a node. In a star graph the center has the highest degree and every other node has a degree of exactly one.

3. Visualize the solution

One cell per node, value = how many edges have touched that node so far

Statusinit

Four nodes, no edges read yet, so every degree starts at zero.

What happens in this step

edges = [[1, 2], [2, 3], [4, 2]]
degree of every node = 0

The row shows nodes 1 to 4 and how many edges have touched each one.
Nothing has been read yet, so all four values are 0.

Step 1 of 5

Steps to visualize

The row below has one cell per node. The label is the node number and the value is its degree so far.
Read the first edge and add one to the degree of both of its nodes.
Read the second edge and do the same.
Whichever node now has a degree of two is the node both edges share, and that node is the center.
The real solution skips the counting and compares the two edges directly, which is why it only ever looks at two edges.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per node, value = how many edges have touched that node so far

Statusinit

Four nodes, no edges read yet, so every degree starts at zero.

What happens in this step

edges = [[1, 2], [2, 3], [4, 2]]
degree of every node = 0

The row shows nodes 1 to 4 and how many edges have touched each one.
Nothing has been read yet, so all four values are 0.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function findCenter(edges) {
  const first = edges[0];
  const second = edges[1];

  if (first[0] === second[0] || first[0] === second[1]) {
    return first[0];
  }

  return first[1];
}

Time: O(1)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`edges = [[1, 2], [2, 3], [4, 2]]`	`2`	example from the docstring
`edges = [[1, 2], [5, 1], [1, 3], [1, 4]]`	`1`	center appears in the left slot of the first edge
`edges = [[1, 2], [2, 3]]`	`2`	smallest valid star graph, only three nodes
`edges = [[3, 1], [3, 2]]`	`3`	center sits in the left slot of both edges
`edges = [[2, 1], [3, 1]]`	`1`	center sits in the right slot of both edges
`edges = [[4, 5], [6, 4], [7, 4]]`	`4`	node numbers that do not start at 1

Find Center of Star Graph