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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
| 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) |
LeetCode 1791. Find Center of Star Graph | Medium | 🏆 Weekly Contest 232 | Algorithm Explained |C++ • Cherry Coding [IIT-G] • 5,979 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