Sponsored
Sponsored
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.
Time Complexity: O(1) since it only involves fixed operations.
Space Complexity: O(1) as no additional data structures are used.
1class Solution:
2 def findCenter(self, edges: List[List[int]]) -> int:
3 u1, v1 = edges[0]
4 u2, v2 = edges[1]
5 if u1 == u2 or u1 == v2:
6 return u1
7 return v1
8In Python, by destructuring the first two edges, the solution checks which node is common between them to find the center.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1#
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.