Leetcode 1791: Find center of Star Graph

In this Leetcode problem, we are given a list of edges representing a star graph. A star graph is a graph where all the edges contain the “center” node. This is the problem statement:

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.

Solution

The first thing to notice is that all edges will contain the center. I know in the final solution I wrote a loop, but in fact we only need 2 edges in the graph to know which is the center.

Indeed, given 2 edges, the center will be the common node between the 2 edges. Instead of doing that directly, my implementation count the number of edges that reach each of the nodes in the graph. As soon as this count is greater than 1, we know that the node is the center.

So, even, if the loop is apparently going though all the edges, the algorithm will return after just 2 iterations in the loop.

The algorithm is still technically O(n), please feel free to improve it to O(1), because I initialize the count array of size n+1. That can be improved by comparing directly edges[0][0], edges[0][1], edges[1][0], and edges[1][1], whichever…