Find Center of Star Graph

🎯

Find Center of Star Graph

easyGRAPHAmazonGoogle

Imagine a social network where one person is the central hub connecting everyone else directly. Finding this person quickly helps in understanding the network's structure.

💡 This problem is about identifying a special node in a graph called the 'center' of a star graph. Beginners often struggle because they might try complex graph traversals when a simple property of the star graph can solve it efficiently.

📋

Problem Statement

Given 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 connected to all other nodes, and no other edges exist. You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi. Return the center node of the given star graph.

3 ≤ n ≤ 10^5edges.length == n - 1edges[i].length == 21 ≤ ui, vi ≤ nui != viThe given edges represent a valid star graph

💡

Example

Input"edges = [[1,2],[2,3],[4,2]]"

Output2

Node 2 is connected to nodes 1, 3, and 4, making it the center of the star.

• Minimum nodes (n=3) → center is the node connected to the other two
• Edges where the first two edges share a common node → that node is center
• Edges where the center node is the smallest numbered node
• Edges where the center node is the largest numbered node

⚠️

Common Mistakes

Assuming the center node is always node 1

Incorrect output if center is a different node

✅ Check edges to find the actual center node instead of hardcoding

Not considering both nodes in edges when counting degrees

Degree counts are incorrect, leading to wrong center

✅ Increment degree counts for both nodes in each edge

Using deep recursion or complex graph traversal unnecessarily

Unnecessary complexity and possible stack overflow

✅ Use simple degree counting or first two edges check instead

Not handling edge cases with minimum nodes

Code may fail or return wrong result for small graphs

✅ Test and handle cases with n=3 explicitly if needed

🧠

Brute Force (Degree Counting)

💡 This approach exists to build intuition by counting how many edges each node has, which directly reveals the center node in a star graph.

Intuition

Since the center node connects to all other nodes, it will have degree n-1. Counting degrees for all nodes and finding the one with degree n-1 identifies the center.

Algorithm

1. Initialize a degree array of size n+1 with zeros.
2. Iterate over each edge and increment the degree count for both nodes.
3. After processing all edges, find the node with degree equal to n-1.
4. Return that node as the center of the star graph.

💡 The main challenge is realizing that the center node's degree is unique and maximal, which simplifies the problem.

</>

Code

from typing import List

def findCenter(edges: List[List[int]]) -> int:
    n = len(edges) + 1
    degree = [0] * (n + 1)
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    for i in range(1, n + 1):
        if degree[i] == n - 1:
            return i

# Driver code
if __name__ == '__main__':
    edges = [[1,2],[2,3],[4,2]]
    print(findCenter(edges))  # Output: 2

Line Notes

n = len(edges) + 1Calculate number of nodes from edges count

degree = [0] * (n + 1)Initialize degree array with zero counts for each node

for u, v in edges:Iterate over each edge to count degrees

degree[u] += 1Increment degree count for node u

degree[v] += 1Increment degree count for node v

for i in range(1, n + 1):Check each node's degree to find the center

if degree[i] == n - 1:Center node connects to all other nodes

return iReturn the identified center node

import java.util.*;

public class FindCenter {
    public static int findCenter(int[][] edges) {
        int n = edges.length + 1;
        int[] degree = new int[n + 1];
        for (int[] edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (degree[i] == n - 1) {
                return i;
            }
        }
        return -1; // Should never reach here for valid star graph
    }

    public static void main(String[] args) {
        int[][] edges = {{1,2},{2,3},{4,2}};
        System.out.println(findCenter(edges)); // Output: 2
    }
}

Line Notes

int n = edges.length + 1;Calculate number of nodes from edges count

int[] degree = new int[n + 1];Initialize degree array for all nodes

for (int[] edge : edges)Iterate over each edge to count degrees

degree[edge[0]]++;Increment degree count for first node

degree[edge[1]]++;Increment degree count for second node

for (int i = 1; i <= n; i++)Check each node's degree to find center

if (degree[i] == n - 1)Center node connects to all others

return i;Return the center node

#include <iostream>
#include <vector>
using namespace std;

int findCenter(vector<vector<int>>& edges) {
    int n = edges.size() + 1;
    vector<int> degree(n + 1, 0);
    for (auto& edge : edges) {
        degree[edge[0]]++;
        degree[edge[1]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (degree[i] == n - 1) {
            return i;
        }
    }
    return -1; // Should not happen
}

int main() {
    vector<vector<int>> edges = {{1,2},{2,3},{4,2}};
    cout << findCenter(edges) << endl; // Output: 2
    return 0;
}

Line Notes

int n = edges.size() + 1;Calculate number of nodes from edges count

vector<int> degree(n + 1, 0);Initialize degree vector with zeros

for (auto& edge : edges)Iterate over edges to count degrees

degree[edge[0]]++;Increment degree for first node

degree[edge[1]]++;Increment degree for second node

for (int i = 1; i <= n; i++)Check each node's degree to find center

if (degree[i] == n - 1)Center node connects to all others

return i;Return the center node

function findCenter(edges) {
    const n = edges.length + 1;
    const degree = new Array(n + 1).fill(0);
    for (const [u, v] of edges) {
        degree[u]++;
        degree[v]++;
    }
    for (let i = 1; i <= n; i++) {
        if (degree[i] === n - 1) {
            return i;
        }
    }
    return -1; // Should not happen
}

// Test
const edges = [[1,2],[2,3],[4,2]];
console.log(findCenter(edges)); // Output: 2

Line Notes

const n = edges.length + 1;Calculate number of nodes from edges count

const degree = new Array(n + 1).fill(0);Initialize degree array with zeros

for (const [u, v] of edges)Iterate over edges to count degrees

degree[u]++;Increment degree for first node

degree[v]++;Increment degree for second node

for (let i = 1; i <= n; i++)Check each node's degree to find center

if (degree[i] === n - 1)Center node connects to all others

return i;Return the center node

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate over all edges once to count degrees, and then iterate over all nodes once to find the center. Both steps are linear in n.

💡 For n=100,000 nodes, this means about 200,000 operations, which is efficient for modern computers.

Interview Verdict: Accepted

This approach is efficient and straightforward, making it a solid baseline solution.

🧠

Better Approach (Check First Two Edges)

💡 This approach leverages the star graph property that the center node must appear in the first two edges, reducing work drastically.

Intuition

Since the center node connects to all others, it must appear in both the first and second edges. Checking the common node between these two edges identifies the center immediately.

Algorithm

1. Extract the two nodes from the first edge.
2. Extract the two nodes from the second edge.
3. Check which node from the first edge appears in the second edge.
4. Return the common node as the center.

💡 The key insight is that the center node is the only node common to the first two edges.

</>

Code

from typing import List

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

# Driver code
if __name__ == '__main__':
    edges = [[1,2],[2,3],[4,2]]
    print(findCenter(edges))  # Output: 2

Line Notes

a, b = edges[0]Unpack first edge nodes

c, d = edges[1]Unpack second edge nodes

if a == c or a == d:Check if first node of first edge is center

return aReturn node a if it is center

else:Otherwise, node b must be center

return bReturn node b as center

public class FindCenter {
    public static int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        int c = edges[1][0], d = edges[1][1];
        if (a == c || a == d) {
            return a;
        } else {
            return b;
        }
    }

    public static void main(String[] args) {
        int[][] edges = {{1,2},{2,3},{4,2}};
        System.out.println(findCenter(edges)); // Output: 2
    }
}

Line Notes

int a = edges[0][0], b = edges[0][1];Extract nodes from first edge

int c = edges[1][0], d = edges[1][1];Extract nodes from second edge

if (a == c || a == d)Check if node a is center

return a;Return node a if center

elseOtherwise node b is center

return b;Return node b as center

#include <iostream>
#include <vector>
using namespace std;

int findCenter(vector<vector<int>>& edges) {
    int a = edges[0][0], b = edges[0][1];
    int c = edges[1][0], d = edges[1][1];
    if (a == c || a == d) {
        return a;
    } else {
        return b;
    }
}

int main() {
    vector<vector<int>> edges = {{1,2},{2,3},{4,2}};
    cout << findCenter(edges) << endl; // Output: 2
    return 0;
}

Line Notes

int a = edges[0][0], b = edges[0][1];Extract first edge nodes

int c = edges[1][0], d = edges[1][1];Extract second edge nodes

if (a == c || a == d)Check if node a is center

return a;Return node a if center

elseOtherwise node b is center

return b;Return node b as center

function findCenter(edges) {
    const [a, b] = edges[0];
    const [c, d] = edges[1];
    if (a === c || a === d) {
        return a;
    } else {
        return b;
    }
}

// Test
const edges = [[1,2],[2,3],[4,2]];
console.log(findCenter(edges)); // Output: 2

Line Notes

const [a, b] = edges[0];Destructure first edge nodes

const [c, d] = edges[1];Destructure second edge nodes

if (a === c || a === d)Check if node a is center

return a;Return node a if center

elseOtherwise node b is center

return b;Return node b as center

⏱

Complexity

TimeO(1)

SpaceO(1)

Only the first two edges are inspected, so the time and space complexity are constant regardless of n.

💡 For any size graph, this approach does a fixed amount of work, making it extremely efficient.

Interview Verdict: Accepted

This is the optimal and simplest approach, ideal for interviews.

🧠

Alternative Approach (Hash Map Frequency Counting)

💡 This approach uses a hash map to count node frequencies from edges, reinforcing the degree counting concept but with a different data structure.

Intuition

The center node appears in every edge, so it will have the highest frequency equal to n-1 in the hash map.

Algorithm

1. Initialize an empty hash map to count node frequencies.
2. Iterate over each edge and increment the count for both nodes in the map.
3. Find the node with frequency equal to n-1 in the map.
4. Return that node as the center.

💡 This approach is similar to degree counting but uses a hash map instead of an array, useful when node labels are not contiguous.

</>

Code

from typing import List

def findCenter(edges: List[List[int]]) -> int:
    freq = {}
    n = len(edges) + 1
    for u, v in edges:
        freq[u] = freq.get(u, 0) + 1
        freq[v] = freq.get(v, 0) + 1
    for node, count in freq.items():
        if count == n - 1:
            return node

# Driver code
if __name__ == '__main__':
    edges = [[1,2],[2,3],[4,2]]
    print(findCenter(edges))  # Output: 2

Line Notes

freq = {}Initialize empty dictionary for frequency counts

n = len(edges) + 1Calculate number of nodes

for u, v in edges:Iterate over edges to count frequencies

freq[u] = freq.get(u, 0) + 1Increment frequency for node u

freq[v] = freq.get(v, 0) + 1Increment frequency for node v

for node, count in freq.items():Iterate over frequency map to find center

if count == n - 1:Center node appears in all edges

return nodeReturn the center node

import java.util.*;

public class FindCenter {
    public static int findCenter(int[][] edges) {
        int n = edges.length + 1;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int[] edge : edges) {
            freq.put(edge[0], freq.getOrDefault(edge[0], 0) + 1);
            freq.put(edge[1], freq.getOrDefault(edge[1], 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getValue() == n - 1) {
                return entry.getKey();
            }
        }
        return -1; // Should not happen
    }

    public static void main(String[] args) {
        int[][] edges = {{1,2},{2,3},{4,2}};
        System.out.println(findCenter(edges)); // Output: 2
    }
}

Line Notes

int n = edges.length + 1;Calculate number of nodes

Map<Integer, Integer> freq = new HashMap<>();Initialize frequency map

for (int[] edge : edges)Iterate over edges to count frequencies

freq.put(edge[0], freq.getOrDefault(edge[0], 0) + 1);Increment frequency for first node

freq.put(edge[1], freq.getOrDefault(edge[1], 0) + 1);Increment frequency for second node

for (Map.Entry<Integer, Integer> entry : freq.entrySet())Iterate over map entries

if (entry.getValue() == n - 1)Check if frequency matches center criteria

return entry.getKey();Return center node

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int findCenter(vector<vector<int>>& edges) {
    int n = edges.size() + 1;
    unordered_map<int, int> freq;
    for (auto& edge : edges) {
        freq[edge[0]]++;
        freq[edge[1]]++;
    }
    for (auto& [node, count] : freq) {
        if (count == n - 1) {
            return node;
        }
    }
    return -1; // Should not happen
}

int main() {
    vector<vector<int>> edges = {{1,2},{2,3},{4,2}};
    cout << findCenter(edges) << endl; // Output: 2
    return 0;
}

Line Notes

int n = edges.size() + 1;Calculate number of nodes

unordered_map<int, int> freq;Initialize frequency map

for (auto& edge : edges)Iterate over edges to count frequencies

freq[edge[0]]++;Increment frequency for first node

freq[edge[1]]++;Increment frequency for second node

for (auto& [node, count] : freq)Iterate over map entries

if (count == n - 1)Check if frequency matches center criteria

return node;Return center node

function findCenter(edges) {
    const freq = new Map();
    const n = edges.length + 1;
    for (const [u, v] of edges) {
        freq.set(u, (freq.get(u) || 0) + 1);
        freq.set(v, (freq.get(v) || 0) + 1);
    }
    for (const [node, count] of freq.entries()) {
        if (count === n - 1) {
            return node;
        }
    }
    return -1; // Should not happen
}

// Test
const edges = [[1,2],[2,3],[4,2]];
console.log(findCenter(edges)); // Output: 2

Line Notes

const freq = new Map();Initialize frequency map

const n = edges.length + 1;Calculate number of nodes

for (const [u, v] of edges)Iterate over edges to count frequencies

freq.set(u, (freq.get(u) || 0) + 1);Increment frequency for node u

freq.set(v, (freq.get(v) || 0) + 1);Increment frequency for node v

for (const [node, count] of freq.entries())Iterate over map entries

if (count === n - 1)Check if frequency matches center criteria

return node;Return center node

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate over all edges once and store counts in a hash map, then iterate over map entries once.

💡 For n=100,000, this means about 200,000 operations plus hash map overhead, still efficient.

Interview Verdict: Accepted

This approach is flexible and useful when node labels are not guaranteed to be contiguous integers.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, the optimal approach checking the first two edges is best due to simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Degree Counting)	O(n)	O(n)	No	N/A	Good to explain intuition, but not optimal
2. Better Approach (Check First Two Edges)	O(1)	O(1)	No	N/A	Optimal approach to code in interview
3. Alternative Approach (Hash Map Frequency Counting)	O(n)	O(n)	No	N/A	Useful if node labels are not contiguous integers

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and finally present the optimal solution.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach of counting degrees.Step 3: Explain the optimal approach using the first two edges.Step 4: Write clean code for the optimal approach.Step 5: Test your code with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 5min → Test: 5min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of graph properties, ability to optimize from brute force to constant time, and clean coding skills.

Common Follow-ups

• What if the graph is not guaranteed to be a star? → Validate input or handle errors.
• Can you solve this if node labels are not contiguous? → Use a hash map for counting.

💡 These follow-ups test your ability to handle variations and robustness in real interviews.

🔍

Pattern Recognition

When to Use

1) Graph with n nodes and n-1 edges, 2) One node connected to all others, 3) Edges form a star shape, 4) Need to find the center node

Signature Phrases

star graphcenter nodeedges connecting all nodes

NOT This Pattern When

Problems involving general graph traversal, shortest paths, or cycles are different patterns.

Similar Problems

Find the Town Judge - similar concept of a unique node connected to all othersFind the Celebrity - identifying a unique person known by everyoneFind the Root of N-ary Tree - finding a unique root node connected to all others

Practice

1. Consider the following Python code implementing flood fill using DFS. Given the input image = [[1,1,1],[1,1,0],[1,0,1]], starting pixel (sr=1, sc=1), and newColor=2, what is the final image returned?

easy

A. [[1,1,1],[1,2,0],[1,0,1]]

B. [[2,2,2],[2,2,0],[2,0,2]]

C. [[2,2,2],[2,2,0],[2,0,1]]

D. [[2,2,2],[2,2,2],[2,2,2]]

Solution

1. Step 1: Trace dfs starting at (1,1) with original color=1

   The pixel at (1,1) is recolored to 2. Its neighbors with color 1 are (0,1), (2,1) is 0 so skipped, (1,0), and (1,2) is 0 skipped.

2. Step 2: Recursively recolor connected pixels with color 1

   All connected pixels with color 1 reachable from (1,1) are recolored to 2, resulting in [[2,2,2],[2,2,0],[2,0,1]]. The pixel at (2,2) remains 1 as it is not connected 4-directionally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only connected pixels with original color changed [OK]

Hint: Trace DFS calls carefully to find connected pixels [OK]

Common Mistakes:

• Changing pixels diagonally connected
• Forgetting to check boundaries

2. Examine the following buggy code for the Keys and Rooms problem:

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [false] * n
    count = 0
    def dfs(room):
        if visited[room]:
            return
        for key in rooms[room]:
            dfs(key)
        visited[room] = true
        nonlocal count
        count += 1
    dfs(0)
    return count == n

What is the bug in this code?

medium

A. Visited marking happens after recursive calls, causing repeated visits

B. Count is incremented before marking visited, causing off-by-one errors

C. Visited array is initialized incorrectly with zeros instead of false

D. DFS is called on room 0 instead of all rooms

Solution

1. Step 1: Analyze visited marking position

   Visited is marked after recursive calls, so the same room can be visited multiple times during recursion.

2. Step 2: Identify consequence of bug

   This causes repeated visits and potentially infinite recursion or incorrect count.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited must be marked before recursion to avoid revisits [OK]

Hint: Mark visited before recursion to prevent repeated visits [OK]

Common Mistakes:

• Marking visited after recursion leads to infinite loops
• Incrementing count before visited marking
• Incorrect initialization of visited array

3. The following code attempts to find the smallest set of vertices to reach all nodes in a DAG. Identify the bug that causes incorrect results on disconnected graphs.

medium

A. Appending nodes to result inside the while loop instead of once at start

B. Not initializing result with zero in-degree nodes before the loop

C. Not handling disconnected components by missing zero in-degree nodes

D. Appending nodes to result inside the while loop causes duplicates

Solution

1. Step 1: Compare with optimal approach

   Optimal code initializes result with all zero in-degree nodes before processing. Here, nodes are appended to result only when popped from queue.

2. Step 2: Identify impact

   This causes nodes that become zero in-degree later to be added to result, inflating the minimal set incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Result should only contain initial zero in-degree nodes [OK]

Hint: Result must contain only initial zero in-degree nodes [OK]

Common Mistakes:

• Adding nodes to result when their in-degree drops to zero
• Confusing queue processing order with minimal set
• Ignoring disconnected components

4. Consider the following buggy code snippet from the BFS approach for Pacific Atlantic Water Flow. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line that appends (0, j) to pacific_queue

B. Missing line that sets atlantic_reachable[m-1][j] = True

C. Line that sets pacific_reachable[0][j] = True

D. Line that appends (m-1, j) to atlantic_queue

Solution

1. Step 1: Check border initialization

   Both oceans' reachable arrays must mark all border cells as True initially.

2. Step 2: Identify missing marking

   For atlantic ocean, bottom row cells (m-1, j) are added to queue but not marked reachable, causing BFS to miss them.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing atlantic_reachable[m-1][j] = True causes incomplete results [OK]

Hint: All border cells must be marked reachable initially [OK]

Common Mistakes:

• Forgetting to mark atlantic_reachable bottom row
• Marking visited after BFS causes infinite loops

5. Suppose the course prerequisites can include self-dependencies (a course requiring itself) and multiple edges between the same courses. Which modification to the Kahn's Algorithm is necessary to correctly detect cycles in this scenario?

hard

A. Ignore self-loops and treat multiple edges as one; no algorithm change needed.

B. Use DFS with coloring instead of Kahn's Algorithm because BFS cannot detect self-loops.

C. Modify in-degree initialization to count self-loops and multiple edges correctly.

D. Add a check to detect self-loops explicitly before running Kahn's Algorithm.

Solution

1. Step 1: Understand impact of self-loops and multiple edges

   Self-loops increase in-degree of a node, and multiple edges increase in-degree counts accordingly.

2. Step 2: Modify in-degree initialization to count all edges accurately

   Counting all edges including self-loops ensures Kahn's Algorithm correctly identifies cycles by never reducing in-degree to zero for cyclic nodes.

3. Step 3: Confirm no other algorithm change needed

   Algorithm logic remains the same; accurate in-degree counts handle these cases.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Proper in-degree counts detect cycles including self-loops [OK]

Hint: Count all edges correctly to detect cycles including self-loops [OK]

Common Mistakes:

• Ignoring self-loops leads to false positives
• Assuming BFS cannot detect self-loops
• Treating multiple edges as single edge incorrectly