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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Center of Star Graph

Number: 1916

Difficulty: Easy

Paid? No

Companies: Microsoft, Amazon

Problem Description

Given an undirected star graph where one node (the center) is connected to every other node, determine which node is the center. The input is provided as a 2D integer array of edges, where each edge connects two nodes.

Key Insights

  • In a star graph, the center node appears in every edge.
  • Comparing just the first two edges is enough to identify the center node.
  • The center node is the common element between these two edges.

Space and Time Complexity

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

Solution

Since the center appears in every edge, we can inspect the first two edges. If the first edge is [u, v] and the second edge is [x, y], then either u or v is the center. Check if u appears in the second edge; if yes, return u, otherwise return v. This simple check is efficient and leverages the structure of the star graph.

Code Solutions

# Function to find the center of the star graph
def findCenter(edges):
    # Extract the nodes from the first edge
    u, v = edges[0]
    # Extract the nodes from the second edge
    x, y = edges[1]
    
    # If the first node of the first edge appears in the second edge, it's the center
    if u == x or u == y:
        return u
    # Otherwise, the second node must be the center
    return v

# Example usage
edges = [[1, 2], [2, 3], [4, 2]]
print(findCenter(edges))  # Expected output: 2
← Back to All Questions