Code Implementation

class Solution:
    def findCenter(self, edges):
        # Each edge connects to the center, so the center must appear in both first two edges
        a, b = edges[0]
        c, d = edges[1]
        # The center is the common node in the first two edges
        return a if a == c or a == d else b
      

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        int a = edges[0][0], b = edges[0][1];
        int c = edges[1][0], d = edges[1][1];
        return (a == c || a == d) ? a : b;
    }
};
      

class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        int c = edges[1][0], d = edges[1][1];
        return (a == c || a == d) ? a : b;
    }
}
      

var findCenter = function(edges) {
    let [a, b] = edges[0];
    let [c, d] = edges[1];
    return (a === c || a === d) ? a : b;
};
      

Problem Description

Given an undirected star graph with n nodes labeled from 1 to n, and an array edges where each element is a pair [u, v] representing an undirected edge between nodes u and v, your task is to find the center node of the star graph.

In a star graph, there is one central node that is connected to every other node, and no other connections exist. The input guarantees that the graph is a valid star graph, meaning there is exactly one such center node and all other nodes connect only to it.

• There is exactly one valid solution.
• Each edge connects two different nodes.
• No two edges connect the same pair of nodes.

Thought Process

To solve the problem, it's important to recognize the unique structure of a star graph. The center node is the only node that appears in every edge because all other nodes are only connected to the center.

A brute-force approach might involve counting the frequency of each node in the edges list and returning the node that appears the most times. However, since the star graph guarantees that only one node is common to all edges, and every other node appears only once, we can optimize further.

By examining just the first two edges, we can determine the center node, since it is the only node present in both. This observation allows us to avoid unnecessary computation and directly identify the answer.

Solution Approach

• Step 1: Take the first two edges from the edges array.
• Step 2: Each edge has two nodes. The center node is the one that appears in both edges.
• Step 3: Compare the nodes in the first edge to those in the second edge.
• Step 4: Return the node that is present in both edges. This is the center of the star graph.

This approach is efficient because it leverages the properties of the star graph: the center is the only node shared by every edge, and we only need the first two edges to find this node.

Example Walkthrough

Suppose edges = [[1,2], [2,3], [4,2]].

• First edge: [1, 2]
• Second edge: [2, 3]

Compare nodes:

• Node 1 (from first edge) is not in the second edge.
• Node 2 (from first edge) is in the second edge.

This matches the star graph structure: node 2 connects to all other nodes.

Time and Space Complexity

• Brute-force approach:
  • Count the frequency of each node by iterating over all edges, which takes O(n) time and O(n) space (for the frequency map).
• Optimized approach (used here):
  • Only examines the first two edges, so the time complexity is O(1).
  • No extra space is required beyond a few variables, so space complexity is O(1).

This makes the solution extremely efficient and well-suited for large inputs.

Summary

By leveraging the unique structure of the star graph, we can identify the center node by simply finding the common element in the first two edges. This approach is both simple and optimal, requiring only constant time and space. The key insight is recognizing that the center node is the only one present in every edge, allowing an elegant and efficient solution.