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.
Example 1:
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.
Example 2:
Input: edges = [[1,2],[5,1],[1,3],[1,4]] Output: 1
Constraints:
3 <= n <= 105edges.length == n - 1edges[i].length == 21 <= ui, vi <= nui != viedges represent a valid star graph.Problem Overview: You are given edges of a star graph. A star graph has one center node connected to every other node, while all other nodes connect only to that center. The task is to identify the center node using the edge list.
Approach 1: Degree Counting (O(n) time, O(n) space)
A star graph has a clear structural property: the center node has degree n-1, while every other node has degree 1. Iterate through the edges and maintain a degree array (or list) where degree[i] tracks how many times node i appears. Each edge increments the degree of its two endpoints. After processing all edges, scan the degree array to find the node whose degree equals edges.length. That node must be the center because it connects to every other node in the graph. This approach uses simple counting and works well when node labels are within a predictable range. The technique is common in graph problems where vertex properties determine the solution.
Approach 2: HashMap / Frequency Counting (O(n) time, O(n) space)
Instead of a fixed-size array, store node frequencies in a hash map. Iterate through each edge and update counts for both nodes using a HashMap or dictionary. Since the center appears in every edge, its frequency will reach n-1. After updating counts, return the node whose frequency equals the total number of edges. This approach is flexible when node labels are sparse or large because the map grows only with encountered nodes. The solution relies on fast O(1) average-time lookups in a hash map and simple frequency counting.
Recommended for interviews: Degree counting is usually the most straightforward explanation. It directly models the definition of a star graph and shows you understand how node degree works in graph structures. The hash map version demonstrates adaptability when node ranges are unknown. Either solution runs in O(n) time, which is optimal because every edge must be examined at least once.
This approach relies on the characteristic that in a star graph, the center node is connected to all other nodes, meaning it appears in every edge. By counting the occurrence of each node in the edges, the one that appears most frequently is the center node.
We derive the center node by comparing nodes in the first two edges. If one node repeats (appears in both pairs) it is the center.
Time Complexity: O(1) since it only involves fixed operations.
Space Complexity: O(1) as no additional data structures are used.
This approach involves using a hashmap or an array to count the degree or frequency of nodes appearing in the edge list. The node with the maximum frequency of appearance will be the center node.
By allocating an array, we keep track of how many times each node appears. The node that reaches a count of 2 first is the center node.
Time Complexity: O(n)
Space Complexity: O(n)
The characteristic of the center point is that it is connected to all other points. Therefore, as long as we compare the points of the first two edges, if there are the same points, then this point is the center point.
The time complexity is O(1), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Degree Counting | Time Complexity: O(1) since it only involves fixed operations. |
| Approach 2: HashMap/Frequency Counting | Time Complexity: O(n) |
| Directly Compare the Points of the First Two Edges | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Degree Counting | O(n) | O(n) | Best when node labels are small or bounded and an array can track degrees efficiently. |
| HashMap / Frequency Counting | O(n) | O(n) | Useful when node labels are large or sparse and a dynamic map is easier than allocating an array. |
Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | codestorywithMIK • codestorywithMIK • 5,638 views views
Watch 9 more video solutions →Practice Find Center of Star Graph with our built-in code editor and test cases.
Practice on FleetCode