algoadvance

Leetcode 1791. Find Center of Star Graph

Problem Statement

Leetcode Problem 1791: Find Center of Star Graph

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] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Clarifying Questions

  1. Will the edges always form a valid star graph?
    • Yes, the problem guarantees that the graph is a valid star graph.
  2. What is the range for the number of nodes n?
    • Given the constraints usually present in Leetcode problems, n can be reasonably small to medium-sized, typically in the order of up to a few thousand.
  3. Can there be multiple center nodes?
    • No, in a valid star graph, there is a unique center node.

Strategy

The star graph has one center node connected to all other nodes. This means that the center node will appear in every edge of the graph. To identify the center node:

  1. We’ll look at the first two edges provided in the array.
  2. One of the nodes common in both edges must be the center node.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int findCenter(vector<vector<int>>& edges) {
        // Check the first two edges to find the common node which is the center
        int node1 = edges[0][0];
        int node2 = edges[0][1];
        
        // The center must be among node1 or node2; it will be whichever appears in the second edge.
        if (edges[1][0] == node1 || edges[1][1] == node1) {
            return node1;
        } else {
            return node2;
        }
    }
};

Explanation

Time Complexity

The time complexity of this solution is (O(1)) because:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI