Find Center of Star Graph

Easy

#1638Time: O(N), where N is the number of nodes. We iterate through N-1 edges to populate the degree counts, and then iterate through up to N nodes to find the center. This results in a linear time complexity.Space: O(N), where N is the number of nodes. We use an auxiliary array of size N+1 to store the degree of each node.

Data structures

Graph

Prompt

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] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. 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 <= 10⁵
edges.length == n - 1
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
The given edges represent a valid star graph.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the property that the center node of a star graph has a degree of n-1, while all other nodes have a degree of 1. We can count the degree of each node by iterating through all the edges. The node with the highest degree is the center.

Algorithm

1. Determine the number of nodes, n, which is edges.length + 1.
1. Create an integer array degree of size n + 1 to store the degree of each node, initialized to zeros.
1. Iterate through each edge in the edges array.
1. For each edge = [u, v], increment degree[u] and degree[v].
1. After iterating through all edges, loop from i = 1 to n.
1. If degree[i] is equal to n - 1, then i is the center node. Return i.

Walkthrough

In a star graph with n nodes, the center node is connected to all other n-1 nodes. This means its degree (the number of edges connected to it) is n-1. All other nodes (the 'spokes' of the star) are only connected to the center, so their degree is 1.

We can use this property to find the center. The algorithm involves two main steps:

Count Degrees: We iterate through the edges array. For each edge [u, v], we increment the degree count for both node u and node v. A hash map or an array can be used to store these counts. Since node labels are from 1 to n, an array of size n+1 is a simple choice.
Find Center: After counting, we iterate through our degree counts. The node whose degree is n-1 (or simply the maximum degree) is the center of the star graph.

For example, given edges = [[1,2],[2,3],[4,2]], there are n = 4 nodes. The center must have a degree of 3. After processing all edges, the degrees would be: degree(1)=1, degree(2)=3, degree(3)=1, degree(4)=1. Clearly, node 2 has a degree of 3, making it the center.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int findCenter(int[][] edges) {6        int n = edges.length + 1;7        int[] degree = new int[n + 1];8        9        for (int[] edge : edges) {10            degree[edge[0]]++;11            degree[edge[1]]++;12        }13        14        for (int i = 1; i <= n; i++) {15            if (degree[i] == n - 1) {16                return i;17            }18        }19        20        return -1; // Should not be reached21    }22}

Complexity

Time

O(N), where N is the number of nodes. We iterate through N-1 edges to populate the degree counts, and then iterate through up to N nodes to find the center. This results in a linear time complexity.

Space

O(N), where N is the number of nodes. We use an auxiliary array of size N+1 to store the degree of each node.

Trade-offs

Pros

It's a general approach that can find the node with the highest degree in any graph.
The logic is straightforward and easy to understand.

Cons

It's not the most efficient solution for this specific problem, as it requires O(N) time and space.
It processes the entire input, which is unnecessary given the problem's guarantees.

This highly efficient approach leverages the core property of a star graph: the center node must be a part of every edge. Therefore, the center node must be the common node present in any two edges. By simply inspecting the first two edges, we can identify the center in constant time.

Algorithm

1. Consider the first edge, edges[0], which contains two nodes, let's call them candidate1 and candidate2.
1. Consider the second edge, edges[1].
1. Check if candidate1 is present in edges[1].
1. If it is, candidate1 is the center. Return candidate1.
1. If not, candidate2 must be the center (due to the star graph property). Return candidate2.

Walkthrough

The problem guarantees that the input graph is a valid star graph. In a star graph, there is a central node connected to all other n-1 nodes. This implies that the center node must appear in every single one of the n-1 edges.

Based on this insight, we don't need to examine all the edges. We only need to look at any two distinct edges to find the node they have in common. The simplest choice is to use the first two edges: edges[0] and edges[1].

Let edges[0] = [u, v] and edges[1] = [x, y]. The center node must be one of the nodes in the first edge, i.e., either u or v. We can check which of these two also appears in the second edge.

If u is equal to x or y, then u is the center.
Otherwise, v must be the center (since a center is guaranteed to exist and be common to both edges).

This check involves a maximum of two comparisons and is independent of the number of nodes n.

1class Solution {2    public int findCenter(int[][] edges) {3        // The center node must be in the first edge.4        int node1 = edges[0][0];5        int node2 = edges[0][1];6        7        // The center node must also be in the second edge.8        // So we check which of node1 or node2 is in the second edge.9        if (node1 == edges[1][0] || node1 == edges[1][1]) {10            return node1;11        } else {12            return node2;13        }14    }15}

Complexity

Time

O(1). The solution only accesses the first two elements of the `edges` array and performs a constant number of comparisons, regardless of the size of the input.

Space

O(1). No extra space is used that scales with the input size.

Trade-offs

Pros

Extremely fast and memory-efficient.
Very simple and concise implementation.

Cons

This solution is highly specialized and only works because the input is guaranteed to be a valid star graph.
It would fail on a general graph or if the input did not represent a star graph.

Solutions

Solution

1class Solution {2public3  int findCenter(int[][] edges) {4    int a = edges[0][0], b = edges[0][1];5    int c = edges[1][0], d = edges[1][1];6    return a == c || a == d ? a : b;7  }8}

1/** * @param {number[][]} edges * @return {number} */ var findCenter =2  function (edges) {3    const [a, b] = edges[0];4    const [c, d] = edges[1];5    return a == c || a == d ? a : b;6  };

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

1class Solution:2    def findCenter(3        self, edges: List[List[int]]) -> int: return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem