Watch 10 video solutions for Find Center of Star Graph, a easy level problem involving Graph. This walkthrough by codestorywithMIK has 5,638 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |