Find Center of Star Graph

Difficulty: Easy | Acceptance: 86.60% | Paid: No Topics: Graph Theory

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi.

Return the center of the given star graph.

• Examples
• Constraints
• Comparison of First Two Edges
• Frequency Counting
• Degree Array

Examples

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

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

Constraints

3 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
1 <= ui, vi <= n
ui != vi
The given edges represent a valid star graph.

Comparison of First Two Edges

Intuition In a star graph, the center node is connected to all other nodes. This means the center node must appear in every single edge provided. Therefore, the center node must be present in both the first edge and the second edge. The intersection of the first two edges is the center.

Steps

• Check if the first node of the first edge (edges[0][0]) is present in the second edge (edges[1]).
• If it is, return edges[0][0].
• Otherwise, the center must be the second node of the first edge (edges[0][1]), so return that.

from typing import List

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        # The center must be in the first edge.
        # Check if the first node of the first edge is in the second edge.
        if edges[0][0] == edges[1][0] or edges[0][0] == edges[1][1]:
            return edges[0][0]
        else:
            return edges[0][1]

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This is the optimal solution as it only inspects the first two edges regardless of input size.

Frequency Counting

Intuition We can count the frequency of each node appearing in the edge list. Since the center node is connected to all other n-1 nodes, it will appear exactly n-1 times in the list of edges. All other nodes appear exactly once.

Steps

• Initialize a hash map (or dictionary) to store node counts.
• Iterate through all edges in the input list.
• For each edge, increment the count for both nodes involved.
• Iterate through the map and return the node that has a count greater than 1 (or specifically n-1).

from typing import List
from collections import defaultdict

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        count = defaultdict(int)
        for u, v in edges:
            count[u] += 1
            count[v] += 1
            # Optimization: if any count reaches 2 (or > 1), it's the center
            # because in a star graph only the center appears more than once.
            if count[u] > 1:
                return u
            if count[v] > 1:
                return v
        return -1

Complexity

• Time: O(E), where E is the number of edges (n-1).
• Space: O(N), to store the frequency counts.
• Notes: While correct, this uses extra memory compared to the constant-time approach.

Degree Array

Intuition Since the nodes are labeled from 1 to n, we can use an array instead of a hash map to count the degrees (number of connections) of each node. This is often faster than a hash map due to better cache locality and lack of hashing overhead.

Steps

• Determine the number of nodes n based on the number of edges (n = edges.length + 1).
• Initialize an integer array degree of size n + 1 with zeros.
• Iterate through the edges and increment the degree for both nodes of each edge.
• Iterate through the degree array and return the index i where degree[i] is greater than 1.

from typing import List

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        # n is edges.length + 1
        n = len(edges) + 1
        degree = [0] * (n + 1)
        
        for u, v in edges:
            degree[u] += 1
            degree[v] += 1
            # Early exit optimization
            if degree[u] > 1:
                return u
            if degree[v] > 1:
                return v
                
        return -1

Complexity

• Time: O(N), where N is the number of nodes.
• Space: O(N), to store the degree array.
• Notes: This approach is generally faster than hash maps for integer keys but uses more space than the O(1) comparison approach.