Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Find Center of Star Graph solution and explanation

EasyGraph4 min read86.6% acceptanceUpdated 9 Apr 2026
Asked atMicrosoftAmazonGoogleBloomberg
Practise Find Center of Star Graph
11:51
Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | codestorywithMIKcodestorywithMIK · 11:51 · 5K viewsWatch on YouTube
9 more videos on this problem
  1. Find Center of Star Graph | 2 Simple Approaches | Leetcode 1791 | codestorywithMIKcodestorywithMIK · 11:51 · 5K views
  2. 1791. Find Center of Star Graph | Indegree - OutdegreeAryan Mittal · 6:02 · 2K views
  3. 1791. Find Center of Star Graph (Leetcode Easy)Programming Live with Larry · 4:23 · 1K views
  4. 1791 Find Center of Star Graph | Solving LeetCode Problem | Coding in Telugu | LVS TalksLVS Logics · 4:54 · 587 views
  5. LeetCode 1791. Find Center of Star Graph Solution Explained - JavaAlgorithms and Data Structures Course · 15:10 · 388 views
  6. Solving LeetCode problem 1791 in APL (Find Center of Star Graph)Rodrigo's APL Corner · 9:47 · 327 views
  7. Find Center of Star Graph - Leetcode 1791 - JavaAlgorial · 6:01 · 258 views
  8. Find Center of Star Graph - Leetcode 1791 - JavaCode With K5KC · 5:23 · 157 views
  9. 1791 Centre of Star Graph #leetcodeTop SWE · 1:11 · 154 views
  10. 1791. Find Center of Star Graph || LEETCODE SOLUTION || GRAPH || C++Abhishweta Gupta · 1:36 · 127 views

The problem

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.

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        u1, v1 = edges[0]
        u2, v2 = edges[1]
        if u1 == u2 or u1 == v2:
            return u1
        return v1
class Solution {
    public int findCenter(int[][] edges) {
        int u1 = edges[0][0], v1 = edges[0][1];
        int u2 = edges[1][0], v2 = edges[1][1];
        if (u1 == u2 || u1 == v2) return u1;
        else return v1;
    }
}
#include <vector>
using namespace std;

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int u1 = edges[0][0], v1 = edges[0][1];
        int u2 = edges[1][0], v2 = edges[1][1];
        if (u1 == u2 || u1 == v2) return u1;
        else return v1;
    }
};
var findCenter = function(edges) {
    const [u1, v1] = edges[0];
    const [u2, v2] = edges[1];
    return (u1 === u2 || u1 === v2) ? u1 : v1;
};
#include <stdio.h>

int findCenter(int** edges, int edgesSize, int* edgesColSize) {
    int u1 = edges[0][0], v1 = edges[0][1];
    int u2 = edges[1][0], v2 = edges[1][1];
    
    if (u1 == u2 || u1 == v2) return u1;
    else return v1;
}
public class Solution {
    public int FindCenter(int[][] edges) {
        int u1 = edges[0][0], v1 = edges[0][1];
        int u2 = edges[1][0], v2 = edges[1][1];
        if (u1 == u2 || u1 == v2) return u1;
        return v1;
    }
}

In Python, by destructuring the first two edges, the solution checks which node is common between them to find the center.

Complexity

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

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.

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
            if count[u] > 1:
                return u
            count[v] += 1
            if count[v] > 1:
                return v
        return -1 # Should not be reached
import java.util.HashMap;

class Solution {
    public int findCenter(int[][] edges) {
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            count.put(u, count.getOrDefault(u, 0) + 1);
            if (count.get(u) > 1) return u;
            count.put(v, count.getOrDefault(v, 0) + 1);
            if (count.get(v) > 1) return v;
        }
        return -1; // Should not be reached
    }
}
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        unordered_map<int, int> count;
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (++count[u] > 1) return u;
            if (++count[v] > 1) return v;
        }
        return -1; // Should never reach here
    }
};
var findCenter = function(edges) {
    const count = {};
    for (const [u, v] of edges) {
        if (count[u]) return u;
        else count[u] = 1;
        if (count[v]) return v;
        else count[v] = 1;
    }
    return -1; // Should never be reached
};
#include <stdio.h>
#include <stdlib.h>

int findCenter(int** edges, int edgesSize, int* edgesColSize) {
    int* count = (int*)calloc(edgesSize + 1, sizeof(int));
    for(int i = 0; i < edgesSize; ++i) {
        int u = edges[i][0], v = edges[i][1];
        if(++count[u] > 1) {
            free(count);
            return u;
        }
        if(++count[v] > 1) {
            free(count);
            return v;
        }
    }
    free(count);
    return -1; // Should never reach here given constraints
}
using System.Collections.Generic;

public class Solution {
    public int FindCenter(int[][] edges) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1];
            if (!count.ContainsKey(u)) count[u] = 0;
            if (++count[u] > 1) return u;
            if (!count.ContainsKey(v)) count[v] = 0;
            if (++count[v] > 1) return v;
        }
        return -1; // Should not be reached
    }
}

This solution leverages a defaultdict to automate counter logic and fetch the node with maximum frequency.

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

function findCenter(edges: number[][]): number {
    for (let num of edges[0]) {
        if (edges[1].includes(num)) {
            return num;
        }
    }
}
func findCenter(edges [][]int) int {
	a, b := edges[0][0], edges[0][1]
	c, d := edges[1][0], edges[1][1]
	if a == c || a == d {
		return a
	}
	return b
}
impl Solution {
    pub fn find_center(edges: Vec<Vec<i32>>) -> i32 {
        if edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] {
            return edges[0][0];
        }
        edges[0][1]
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Degree Counting

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

Approach 2: HashMap/Frequency Counting

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

Directly Compare the Points of the First Two Edges–

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.

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.

Comments

Next problem · similarMaximum Star Sum of a GraphMedium
Now write it yourselfClose this page and solve Find Center of Star Graph in the editor, without looking.
Practise Find Center of Star Graph