Leetcode – Find Center of Star Graph Solution

Spread the love

The ‘Find Center of Star Graph’ is a classic graph-related problem often encountered in coding interviews and competitive programming. This problem is an excellent way to demonstrate your understanding of graph theory, arrays, and hash tables. In this article, we will dissect the problem, discuss various approaches, and analyze their time and space complexities.

Problem Statement

You are given an undirected star graph, modeled as a 2D array edges. The graph consists of n nodes labeled from 1 to n, and exactly n - 1 edges. A star graph is a graph that forms a star shape, and it has one node (the center) connected to every other node through exactly one edge.

Your task is to find the center of the given star graph.

Examples

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

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

Approach 1: Frequency Count using Hash Table

A star graph has one center node connected to all other nodes. Thus, the center node will appear in every edge. We can leverage this property to solve the problem.

Algorithm Steps

  1. Initialize an empty hash table to keep track of node frequencies.
  2. Loop through each edge in the edges array.
  3. For each node in the edge, increment its frequency in the hash table.
  4. Return the node with a frequency equal to n - 1.

Python Code

from collections import defaultdict

def findCenter(edges):
    freq = defaultdict(int)
    for u, v in edges:
        freq[u] += 1
        freq[v] += 1
    for node, count in freq.items():
        if count == len(edges):
            return node

Time and Space Complexity

  • Time Complexity: O(n) where n is the number of edges.
  • Space Complexity: O(n) for storing the frequency of each node.

Approach 2: Frequency Count using Array

Since the nodes are labeled from 1 to n, we can use a list to store the frequency of each node instead of a hash table. This will reduce the constant factors involved in the hash table operations.

Python Code

def findCenter(edges):
    n = len(edges) + 1
    freq = [0] * (n + 1)
    for u, v in edges:
        freq[u] += 1
        freq[v] += 1
    for node in range(1, n + 1):
        if freq[node] == n - 1:
            return node

Time and Space Complexity

  • Time Complexity: O(n)
  • Space Complexity: O(n)

Approach 3: Observation-based Optimization

Since the center of the star graph appears in every edge, we can make an observation that the center will appear in any two random edges. This can help us solve the problem in constant time.

Algorithm Steps

  1. Pick the first edge and any other edge from the list edges.
  2. Find the common node between these two edges.
  3. Return the common node.

Python Code

def findCenter(edges):
    edge1, edge2 = edges[0], edges[1]
    if edge1[0] == edge2[0] or edge1[0] == edge2[1]:
        return edge1[0]
    return edge1[1]

Time and Space Complexity

  • Time Complexity: O(1)
  • Space Complexity: O(1)

Conclusion

The ‘Find Center of Star Graph’ problem serves as an excellent demonstration of the utility of understanding problem-specific properties. This problem could be solved in linear time using hash tables or arrays. However, by recognizing the star graph’s unique characteristics, we were able to optimize the solution to constant time.

Leave a Reply