We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Center of Star Graph

Difficulty: Easy

Problem Description

Given an undirected star graph consisting of n nodes labeled from 1 to n, where there is one center node connected to every other node with exactly n - 1 edges, return the center of the star graph from a given 2D integer array of edges.

Key Insights

  • A star graph has one center node that connects to all other nodes.
  • The center node will appear in every edge of the graph.
  • Since there are n - 1 edges, we only need to check the first two edges to identify the center node.

Space and Time Complexity

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

Solution

To solve this problem, we can utilize the fact that the center node appears in all edges. By examining the first two edges in the input, we can determine which node is the center. We can simply check which of the two nodes appears in the third edge, as this will be the center node.

Code Solutions

def findCenter(edges):
    # Check the first edge
    a, b = edges[0]
    # Check the second edge
    c, d = edges[1]
    
    # Since the center connects to all, return the one which appears in both edges
    if a == c or a == d:
        return a
    return b
← Back to All Questions