Find Center of Star Graph

📋

Problem

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.

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

Edge cases: Minimum nodes (n=3) → center is the node connected to the other twoEdges where the first two edges share a common node → that node is centerEdges where the center node is the smallest numbered node

</>

IDE

def findCenter(edges: list[list[int]]) -> int:public int findCenter(int[][] edges)int findCenter(vector<vector<int>>& edges)function findCenter(edges)

def findCenter(edges):
    # Write your solution here
    pass

class Solution {
    public int findCenter(int[][] edges) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findCenter(vector<vector<int>>& edges) {
    // Write your solution here
    return 0;
}

function findCenter(edges) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: First node of first edgeAssuming the first node in the first edge is always the center without checking the second edge.✅ Return the node common to the first two edges instead of blindly returning the first node.

Wrong: Node with highest frequency but not centerIncorrect frequency counting or not counting both nodes in edges properly.✅ Count both nodes in each edge and return the node with frequency n-1.

Wrong: Smallest node alwaysAssuming center is always the smallest node without checking edges.✅ Check the common node in first two edges regardless of node values.

Wrong: Largest node alwaysAssuming center is always the largest node without checking edges.✅ Check the common node in first two edges regardless of node values.

✓

Test Cases

Try testing your solution on the smallest star graph and cases where center is smallest or largest node.

Consider edge cases where greedy or partial checks fail; verify your logic on node occurrences.

Think about the time complexity of your approach; can you find the center in constant time?

t1_01basic

Input{"edges":[[1,2],[2,3],[4,2]]}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Check which node appears in all edges.

💡 The center node appears in every edge; count node occurrences.

💡 Compare the first two edges; the common node is the center.

Why it failed: Incorrect output means you likely did not identify the node common to all edges. Fix by checking the first two edges and returning their common node.

✓ Correctly identified the center node by checking node occurrences.

t1_02basic

Input{"edges":[[3,4],[3,2],[3,1],[3,5]]}

Expected3

⏱ Performance - must finish in 2000ms

Node 3 connects to all other nodes 1, 2, 4, and 5, so it is the center.

💡 Look for the node that appears in every edge.

💡 Count the frequency of nodes in edges; the center appears n-1 times.

💡 Check the first two edges for a common node; that node is the center.

Why it failed: Wrong output suggests failure to identify the node common to all edges. Fix by returning the node common to the first two edges.

✓ Center node correctly found by identifying the common node in first two edges.

t2_01edge

Input{"edges":[[1,2],[1,3]]}

Expected1

⏱ Performance - must finish in 2000ms

Minimum nodes (n=3). Node 1 connects to nodes 2 and 3, so it is the center.

💡 Test the smallest valid star graph with 3 nodes.

💡 The center node connects to both other nodes.

💡 Check the first two edges for the common node; it is the center.

Why it failed: Failed on minimum nodes test; likely did not handle smallest input correctly. Fix by ensuring code works for n=3 and returns the node common to both edges.

✓ Correctly handled minimum nodes case.

t2_02edge

Input{"edges":[[5,1],[5,2],[5,3],[5,4]]}

Expected5

⏱ Performance - must finish in 2000ms

Center node is the largest numbered node (5) connected to all others.

💡 Center node can be the largest node number.

💡 Do not assume center is smallest node; check edges carefully.

💡 Find the node common to the first two edges; that node is the center.

Why it failed: Incorrect output due to assuming center is smallest node. Fix by checking the common node in first two edges regardless of node values.

✓ Correctly identified center node even when it is the largest node.

t2_03edge

Input{"edges":[[2,1],[2,3],[2,4],[2,5]]}

Expected2

⏱ Performance - must finish in 2000ms

Center node is the smallest numbered node (2) connected to all others.

💡 Center node can be the smallest node number.

💡 Check the first two edges for the common node.

💡 Return the node common to the first two edges as center.

Why it failed: Incorrect output due to not handling smallest node as center. Fix by returning the node common to first two edges.

✓ Correctly identified center node when it is the smallest node.

t3_01corner

Input{"edges":[[1,2],[3,2],[4,2],[5,2],[6,2]]}

Expected2

⏱ Performance - must finish in 2000ms

Greedy trap: picking first node of first edge (1) is wrong; center is node 2.

💡 Don't assume the first node of the first edge is center.

💡 Check the common node between first two edges to find center.

💡 Return the node that appears in both first edges, not just the first node.

Why it failed: Failed greedy trap test by returning first node of first edge. Fix by returning the node common to first two edges.

✓ Correctly avoided greedy trap by checking first two edges.

t3_02corner

Input{"edges":[[7,3],[3,1],[3,2],[3,4],[3,5]]}

Expected3

⏱ Performance - must finish in 2000ms

Off-by-one error: center node 3 is not first node in all edges; must check both nodes.

💡 Check both nodes in each edge, not just first node.

💡 Find the node common to first two edges.

💡 Return the node that appears in both first two edges.

Why it failed: Failed by only checking first node of edges. Fix by checking both nodes in first two edges to find common node.

✓ Correctly handled node positions in edges.

t3_03corner

Input{"edges":[[10,1],[10,2],[10,3],[10,4],[10,5],[10,6],[10,7],[10,8],[10,9]]}

Expected10

⏱ Performance - must finish in 2000ms

Hash map frequency confusion: must not count frequencies incorrectly; center appears n-1 times.

💡 Count node frequencies correctly.

💡 Center node frequency equals n-1 edges.

💡 Return node with frequency n-1 from edges.

Why it failed: Incorrect frequency counting caused wrong output. Fix by counting both nodes in each edge and returning node with frequency n-1.

✓ Correctly counted frequencies and identified center.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 edges; O(n) solution must complete within 2 seconds.

💡 Optimal solution runs in O(n) time.

💡 Avoid nested loops; use constant time checks.

💡 Check only first two edges to find center node.

Why it failed: TLE due to O(n^2) or higher complexity. Fix by using O(n) or O(1) approach checking first two edges only.

✓ Solution runs in O(n) time and passes performance test.

Practice

1. Consider the following Python code implementing Kahn's Algorithm for course scheduling. What is the return value of canFinish(3, [[1,0],[2,1]]) after the while loop completes?

easy

A. false

B. true

C. Raises an error due to empty queue

D. Returns true only if numCourses is 2

Solution

1. Step 1: Initialize graph and in-degree arrays

   Graph: 0 -> [1], 1 -> [2], 2 -> []. In-degree: [0,1,1]. Queue starts with nodes having in-degree 0 -> [0].

2. Step 2: Process queue and update count

   Pop 0, count=1; decrement in-degree of 1 to 0, enqueue 1. Pop 1, count=2; decrement in-degree of 2 to 0, enqueue 2. Pop 2, count=3; queue empty.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All courses processed, so return true [OK]

Hint: Count equals numCourses means no cycle [OK]

Common Mistakes:

• Off-by-one error in count increment
• Misunderstanding queue initialization
• Confusing in-degree decrement timing

2. You are given a list of edges representing an undirected graph with n nodes labeled from 0 to n-1. You need to determine if the graph forms a valid tree. Which algorithmic approach guarantees an optimal solution to check both connectivity and absence of cycles efficiently?

easy

A. Use a greedy algorithm that adds edges one by one and checks if the graph remains connected.

B. Apply dynamic programming to count the number of ways to reach each node and detect cycles.

C. Sort edges and use binary search to detect cycles and connectivity.

D. Perform a BFS or DFS traversal to detect cycles and verify that all nodes are connected.

Solution

1. Step 1: Understand problem requirements

   The problem requires checking if the graph is connected and contains no cycles, which defines a tree.

2. Step 2: Identify suitable algorithm

   BFS or DFS traversal can detect cycles by tracking visited nodes and parent relationships, and also verify connectivity by ensuring all nodes are visited.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS/DFS simultaneously checks connectivity and cycles efficiently [OK]

Hint: Trees have n-1 edges and no cycles [OK]

Common Mistakes:

• Assuming greedy edge addition ensures connectivity
• Using DP which is unrelated here

3. Consider the following Union-Find based code snippet to check if a graph is bipartite. Given the graph adjacency list [[1,3],[0,2],[1,3],[0,2]], what is the return value of isBipartite(graph)?

easy

A. true

B. false

C. Raises an exception

D. null (infinite loop)

Solution

1. Step 1: Trace union operations for node 0

   Node 0 neighbors: 1 and 3. Union(1,3) is called. Since 1 and 3 are separate, union succeeds.

2. Step 2: Trace union operations for other nodes

   For node 1 neighbors: 0 and 2. Union(0,2) is called. 0 and 2 are separate, union succeeds. Similarly for node 2 and 3, unions succeed without conflict.

3. Step 3: Check for conflicts

   However, the union-find approach here incorrectly unions neighbors of the same node, which can cause false positives. The code logic is flawed for bipartite checking.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   The code returns false due to a union conflict, indicating the graph is not bipartite [OK]

Hint: Union-Find returns false only on odd cycle detection [OK]

Common Mistakes:

• Confusing union arguments order
• Assuming union returns true on conflict

4. Consider this buggy DFS code for rotting oranges. Which line contains the subtle bug causing incorrect rot timing?

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    time_grid = [[-1]*cols for _ in range(rows)]
    max_time = 0

    def dfs(r, c, time):
        nonlocal max_time
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == 0:
            return
        if time_grid[r][c] != -1 and time_grid[r][c] <= time:
            return
        time_grid[r][c] = time
        max_time = max(max_time, time)
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 1 or grid[nr][nc] == 2:
                    dfs(nr, nc, time + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                dfs(r, c, 0)
    return max_time

medium

A. Line updating max_time = max(max_time, time)

B. Line setting time_grid[r][c] = time

C. Line checking if grid[nr][nc] == 1 or grid[nr][nc] == 2 without time_grid comparison

D. Line returning if time_grid[r][c] != -1 and time_grid[r][c] <= time

Solution

1. Step 1: Identify rot spread condition

   Rot should spread to fresh oranges or to rotten oranges only if it improves their rot time.

2. Step 2: Check neighbor condition

   Line checking neighbors lacks time_grid comparison for rotten oranges, causing unnecessary or premature DFS calls.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing time check causes incorrect rot timing and possible infinite recursion [OK]

Hint: Rot spread must consider time_grid to avoid premature revisits [OK]

Common Mistakes:

• Ignoring time_grid for rotten neighbors
• Updating max_time incorrectly
• Not pruning DFS calls

5. Suppose the problem is modified so that diagonal neighbors (top-left, top-right, bottom-left, bottom-right) are also considered connected. Which of the following changes to the BFS algorithm correctly adapts to this new requirement without double counting or missing cells?

hard

A. Add diagonal neighbors to the neighbor list and keep the rest of the BFS code unchanged

B. Use DFS instead of BFS because BFS cannot handle diagonal connections

C. Keep neighbor list unchanged but run BFS twice, once for horizontal/vertical and once for diagonals

D. Add diagonal neighbors to the neighbor list and also mark visited cells immediately when enqueuing them

Solution

1. Step 1: Add diagonal neighbors to the neighbor list

   Include all 8 directions: horizontal, vertical, and diagonal neighbors.

2. Step 2: Mark cells as visited when enqueuing

   This prevents adding the same cell multiple times from different neighbors, avoiding double counting.

3. Step 3: Keep BFS traversal logic unchanged otherwise

   Running BFS twice or switching to DFS is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Mark visited on enqueue avoids duplicates with expanded neighbors [OK]

Hint: Mark visited on enqueue when neighbors increase [OK]

Common Mistakes:

• Not marking visited on enqueue causing duplicates
• Running BFS multiple times unnecessarily
• Thinking BFS can't handle diagonals