[O(1) Time and Space] LeetCode 1791. Find Center of Star Graph - Easy Solution | Go

Link 👉🏻 1791. Find Center of Star Graph

Description

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.

Example 1:

LeetCode 1791. Find Center of Star Graph -- Example 1

• 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:

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

Constraints:

• 3 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi
• The given edges represent a valid star graph.

Intuition

In a star ⭐️ graph, the center node will appear in each of the edges which means every node will contain the center node. So, we just need to find the common node in the first two edges. ✨

Approach

1. Check if the first node of the first edge is equal to the first node of the second edge or the second node of the second edge. If true, return the first node of the first edge.
2. Otherwise, return the second node of the first edge.

Complexity

• Time complexity:
• Space complexity:

Code

func findCenter(edges [][]int) int {
	if edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] {
		return edges[0][0]
	}
	return edges[0][1]
}