LeetCode 1791 - Find Center of Star Graph

LeetCode Problem 1791

Difficulty: 🟢 Easy
Topics: Graph Theory

Solution

Problem Understanding

The problem is asking us to identify the center node of a star graph. A star graph is a very specific type of graph with n nodes: there is one node called the center, and it is connected to all other n-1 nodes. Every other node in the graph has exactly one connection, which is to the center. The input consists of a list of edges, where each edge is a pair of nodes [u, v] indicating a bidirectional connection. Our goal is to return the label of the center node.

The constraints tell us several important points. First, 3 <= n <= 10^5 indicates that the number of nodes can be large, so we need a solution that is linear or nearly linear in time. Second, edges.length == n - 1 is a property of a tree-like graph structure and reinforces that the graph is a valid star graph, so we do not need to check for disconnected nodes or cycles. Third, ui != vi ensures no self-loops, which simplifies logic.

Key edge cases include scenarios where the center appears in the first edge or the second edge. The naive assumption that the first node of the first edge is the center could fail if the first edge happens to connect two peripheral nodes. The problem guarantees that the input is a valid star, so there is exactly one center, avoiding ambiguity.

Approaches

A brute-force approach would involve counting the occurrences of each node in all edges. The node that appears in all n-1 edges is the center. While correct, this method requires iterating over all edges and maintaining a frequency count, which is unnecessary for this problem and adds extra space complexity.

The key observation is that in a star graph, the center node must appear in every edge. Since there are n-1 edges, the center node is guaranteed to appear in both of the first two edges. Therefore, the center must be the node that is common to the first two edges. This insight allows us to determine the center in constant time and space, without scanning the entire graph.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Count occurrences of each node in all edges
Optimal	O(1)	O(1)	Check the first two edges for the common node

Algorithm Walkthrough

1. Take the first edge, [a, b].
2. Take the second edge, [c, d].
3. Compare the nodes of the first edge with the nodes of the second edge:

• If a is equal to c or d, then a is the center.
• Otherwise, b must be the center (since there is guaranteed to be exactly one center, it must appear in both edges).

4. Return the identified center.

Why it works: In a star graph, the center node is connected to every other node. Therefore, it must appear in the first two edges. Comparing just these edges is sufficient to identify the center without scanning all edges.

Python Solution

from typing import List

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        a, b = edges[0]
        c, d = edges[1]
        
        if a == c or a == d:
            return a
        else:
            return b

The Python solution starts by unpacking the first two edges. We then check which node appears in both edges. The first edge gives us candidates a and b, and the second edge gives nodes c and d. If a matches either c or d, it is the center. Otherwise, b must be the center. This implementation directly follows the optimal algorithm and runs in constant time.

Go Solution

func findCenter(edges [][]int) int {
    a, b := edges[0][0], edges[0][1]
    c, d := edges[1][0], edges[1][1]
    
    if a == c || a == d {
        return a
    }
    return b
}

The Go solution mirrors the Python approach. We extract the first two edges and check for the node common to both. Go requires explicit indexing into slices, but the logic is identical. There is no need for maps or additional storage, so space remains constant.

Worked Examples

Example 1: edges = [[1,2],[2,3],[4,2]]

Step	Variables	Action
1	a=1, b=2	First edge unpacked
2	c=2, d=3	Second edge unpacked
3	Compare a with c,d	1 != 2 and 1 != 3 → False
4	Return b	2 is center

Example 2: edges = [[1,2],[5,1],[1,3],[1,4]]

Step	Variables	Action
1	a=1, b=2	First edge unpacked
2	c=5, d=1	Second edge unpacked
3	Compare a with c,d	1 == d → True
4	Return a	1 is center

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only the first two edges are checked; independent of n
Space	O(1)	Only a few variables are used; no extra storage needed

Since the algorithm only inspects two edges and uses no extra memory, it achieves the optimal theoretical limits.

Test Cases

# test cases
assert Solution().findCenter([[1,2],[2,3],[4,2]]) == 2  # center in second edge
assert Solution().findCenter([[1,2],[5,1],[1,3],[1,4]]) == 1  # center in first and second edges
assert Solution().findCenter([[3,4],[4,2],[4,1]]) == 4  # center is middle node
assert Solution().findCenter([[1000,2],[3,1000],[1000,4]]) == 1000  # large node numbers
assert Solution().findCenter([[1,2],[2,3]]) == 2  # smallest valid n=3

Test	Why
[[1,2],[2,3],[4,2]]	Center appears in second edge
[[1,2],[5,1],[1,3],[1,4]]	Center appears in first and second edges
[[3,4],[4,2],[4,1]]	Center is a node not in first position
[[1000,2],[3,1000],[1000,4]]	Tests large node values
[[1,2],[2,3]]	Tests smallest allowed graph, n=3

Edge Cases

One important edge case is when the center is the second node of the first edge. A naive solution that always picks the first node would fail, but our comparison with the second edge ensures correctness.

Another edge case is when node labels are very large or non-sequential. Since we do not rely on arrays indexed by node labels, only on equality checks, our solution handles arbitrary labels correctly.

A third edge case is the smallest possible star graph with n=3. The algorithm still works because the first two edges are sufficient to identify the center, even with the minimum number of nodes.