Find Center of Star Graph - Practice Coding Problems

Find Center of Star Graph - Problem

Graph Easy

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] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.

Input & Output

Example 1 — Basic Star Graph

$ Input: edges = [[1,2],[2,3],[4,2]]

› Output: 2

💡 Note: Node 2 is connected to all other nodes (1, 3, and 4), making it the center of the star graph

Example 2 — Different Center

$ Input: edges = [[1,2],[5,1],[1,3],[1,4]]

› Output: 1

💡 Note: Node 1 is connected to all other nodes (2, 3, 4, and 5), making it the center

Example 3 — Minimum Star Graph

$ Input: edges = [[1,2]]

› Output: 1

💡 Note: With only one edge, either node can be considered center, but node 1 appears first

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

Visualization

Tap to expand

Understanding the Visualization

Input

2D array of edges representing connections

Process

Find node that appears in most connections

Output

Return the center node number

Key Takeaway

🎯 Key Insight: The center node appears in every edge, so checking the first two edges is enough

Asked in

F Facebook 25 G Google 20 A Amazon 15

The key insight is that in a star graph, the center node appears in every edge. We can find it by checking which node is common in the first two edges. Best approach uses two-edge check with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two-Edge Check	O(1)	O(1)	Check only the first two edges - the center must appear in both
Count All Node Degrees	O(n)	O(n)	Count how many edges each node appears in, return the one with n-1 edges

Two-Edge Check — Algorithm Steps

Step 1: Take first two edges
Step 2: Find the common node between them
Step 3: Return the common node as center

Visualization

Tap to expand

Step-by-Step Walkthrough

First Two Edges

Take edges[0] and edges[1]

Find Common Node

Center must appear in both edges

Result

Return the common node

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int edges[][2], int edgeCount) {
    // In a star graph, center appears in every edge
    // So it must be common in first two edges
    int edge1_0 = edges[0][0], edge1_1 = edges[0][1];
    int edge2_0 = edges[1][0], edge2_1 = edges[1][1];
    
    // Check which node is common
    if (edge1_0 == edge2_0 || edge1_0 == edge2_1) {
        return edge1_0;
    } else {
        return edge1_1;
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int edges[1000][2];
    int edgeCount = 0;
    char *ptr = line + 1;  // Skip first '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            edges[edgeCount][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            edgeCount++;
        }
        ptr++;
    }
    
    int result = solution(edges, edgeCount);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Only accesses first two edges, constant time operations

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~8 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Edge Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler