Find Center of Graph

Google Interview Question

Poll of the Day

---

Problem Overview

Difficulty: Easy
LeetCode Pattern: N/A

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 graph.

Example

Input:
· edges = [[1,2],[2,3],[4,2]]
Output: 
· 2
Reason:
· 2 is the center of this graph

---

Video Solution

---

Step 1: Clarify Requirements

• Can edges be empty?

  • No.

• Can there be multiple centers?

  • No.

• Is graph guaranteed to have a center?

  • Yes.

---

Step 2: Discuss Approaches

Approach 1: Count Node Degree

• Logic:

  • Use a map to:

    • Count # of edges for each node

  • Return node with max degree

• Big O:

  • Time Complexity: O(n)

  • Space Complexity: O(n)

Approach 2: Check Two Edges (Optimal)

• Logic:

  • We only need to check first 2 edges.

  • Node common to both is the center.

• Big O:

  • Time Complexity: O(1)

  • Space Complexity: O(1)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if no guaranteed center?

  • Check degrees or connectivity.

• What if graph is directed?

  • Center = node with all incoming edges.

---

👨‍💻 Need Interview Practice?

• Book a 1:1 with me

• Book Here: Booking URL