Find center of star graph

Implementation

• Brute force approach
  • Time complexity - O($n^2$)
  • Space complexity - O(n)

class Solution:

    def findCenter(self, edges: List[List[int]]) -> int:

        # Brute force approach

        nodes, count = defaultdict(int), 0

        for i in edges:

            count += 1

            for j in i:

                nodes[j] += 1

        for k in nodes:

            if nodes[k] >= len(nodes) - 1:

                return k

• Optimal approach
  • Time complexity - O(1)
  • Space complexity - O(1)

class Solution:

    def findCenter(self, edges: List[List[int]]) -> int:

        # Optimal solution

        firstEdge, secondEdge = edges[0], edges[1]

        if (firstEdge[0] == secondEdge[0] or firstEdge[0] == secondEdge [1]):

            return firstEdge[0]

        else:

            return firstEdge[1]

• The reason this solution works is because we rely on the following predicates:
  • A leaf node can have no more than one edge given it must adhere to a star graphs design
  • For a single node to have $\ge$ 2 edges would mean that it is indefinitely the center of the graph
  • Additionally the center node must be mentioned in each edge so we search for it to see if it is there in a source of destination node in the first two edges in the edges array, once we find it we determine what the edge is.
• Finally, the solution has a time and space complexity of O(1)