Problem

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.

Examples

Example 1:

 graph TB
     1
     1 --- 2
     2 --- 3
     2 --- 4
  
1
2
3

Input: edges =[[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

 graph TB
     2
     3
     2 --- 1
     3 --- 1
     1 --- 4
     1 --- 5
  
1
2

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

Solution

Method 1 - Count number of edges per node

We have total n edges in star graph, and n+1 nodes. For all nodes, the center node will have n edges connected to it. So, we sill just count the number of edges per node, and return the node which has n edges connected to it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {

	public int findCenter(int[][] edges) {
		int n = edges.length;

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

		for (int i = 0; i < n; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            freq.put(u, freq.getOrDefault(u, 0) + 1);
            freq.put(v, freq.getOrDefault(v, 0) + 1);
		}

		int center = -1;
        System.out.println(freq);
		for (var pair: freq.entrySet()) {
			if (pair.getValue() == n) {
				return pair.getKey();
			}
		}

		return center;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Just Look at 2 edges

We can notice that the center node has to appear in every edge. This mean the node that appears in both edge[0] and edge[1] will be the center node. So, we just need 2 edges to check that, and find out the common node OR center node.

Here is the video explanation:

Code

1
2
3
4
5
6
7

class Solution {
	public int findCenter(int[][] edges) {
		// if first node of edge-0 occurs in edge-1 as well, it's the center one
		// otherwise, the second node of edge-0 will be center node for sure
		return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0]: edges[0][1];
	}
}

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)