Skip to main content
Talentd

Find Center of Star Graph - Solution & Explanation

EasyGraph12 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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 <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • The given edges represent a valid star graph.

Approach Overview

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.

Approach 1: Approach 1: Degree Counting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) since it only involves fixed operations.
Space Complexity: O(1) as no additional data structures are used.

Try this approach in the editor →

Approach 2: Approach 2: HashMap/Frequency Counting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Directly Compare the Points of the First Two Edges

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Degree Counting

Time Complexity: O(1) since it only involves fixed operations.
Space Complexity: O(1) as no additional data structures are used.

Approach 2: HashMap/Frequency Counting

Time Complexity: O(n)
Space Complexity: O(n)

Directly Compare the Points of the First Two Edges—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Degree CountingO(n)O(n)Best when node labels are small or bounded and an array can track degrees efficiently.
HashMap / Frequency CountingO(n)O(n)Useful when node labels are large or sparse and a dynamic map is easier than allocating an array.

Video Solution

Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | codestorywithMIK • codestorywithMIK • 5,921 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Center of Star Graph easy or hard?
Find Center of Star Graph is classified as an Easy problem. The key observation is that the center node appears in every edge of the star graph, allowing a straightforward O(n) counting solution.
Find Center of Star Graph Python/Java solution
In Python or Java, iterate through the edges and update counts in a dictionary or HashMap. The node whose count becomes edges.length is the center. The same logic can also be implemented with an integer array if node labels are within range.
How to solve Find Center of Star Graph in O(n)?
Iterate through the edges and count how many times each node appears. Use either an array (degree counting) or a hash map (frequency counting). Since the center connects to all other nodes, it appears in every edge and will have frequency n-1.
What is the best approach for Find Center of Star Graph?
Degree counting is the most direct approach. Count how many times each node appears in the edge list. In a star graph with n nodes, the center node has degree n-1 while every other node has degree 1. The node whose count equals the number of edges is the center, giving an O(n) time solution.
Is Find Center of Star Graph asked at Google/Amazon/Meta?
Graph basics and degree-based reasoning problems frequently appear in coding interviews at companies like Amazon, Google, and Meta. This problem specifically tests understanding of graph structure and quick pattern recognition, which are common interview themes.
What data structure is used in Find Center of Star Graph?
The most common data structures are arrays for degree counting or a hash map for frequency tracking. Both store how many times each node appears in the edge list and allow constant-time updates while iterating through edges.
What is the time complexity of Find Center of Star Graph?
The optimal solutions run in O(n) time where n is the number of edges. Each edge is processed once to update node counts. Space complexity is O(n) when using an array or hash map to store node frequencies.

Ready to solve this problem?

Practice Find Center of Star Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Star Sum of a Graph