Problem 20.1 · Graph FundamentalsEasy

Find Center of Star Graph

What it teaches: Reading structure from edges: the centre is the node shared by every edge, so two edges are enough.

Practise it on judges as “Find Center of Star Graph”.

The problem

A star graph has one centre connected to every other node, and no other edges. Given its edges, return the centre.

Example 1

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2

Constraints

3 ≤ n ≤ 10⁵
edges.length = n − 1
The input is a star

Pattern clues in the wording

→ A special graph shape is guaranteed

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findCenter(int[][] edges) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	edges = [[1,2],[2,3],[4,2]]	2
2	edges = [[1,2],[5,1],[1,3],[1,4]]	1

From slow to fast

Approaches

1. Compare two edges · O(1)2. Degree count · O(n)

Compare two edges

Time O(1) Space O(1)

The node that appears in both edges[0] and edges[1] is the centre.

Approach 1

class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        return a == edges[1][0] || a == edges[1][1] ? a : b;
    }
}

Verdict: Uses the guarantee fully.

Degree count

Time O(n) Space O(n)

Count degrees; the node with degree n − 1 is the centre. Works for checking any graph.

Approach 2

class Solution {
    public int findCenter(int[][] edges) {
        int n = edges.length + 1;
        int[] deg = new int[n + 1];
        for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
        for (int v = 1; v <= n; v++) if (deg[v] == n - 1) return v;
        return -1;
    }
}

Verdict: General but unnecessary here.

Before you submit

Edge cases and common mistakes

Test these inputs

Three nodes
Centre listed second in edges

Mistakes people make

Building an adjacency list when two edges suffice.

Interview

Follow-up questions

How would you verify the input is really a star?