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.

Example:

Input:

edges = [[1,2],[2,3],[4,2]]

Output:

2

Clarifying Questions

1. Q: What is the minimum value for n?
   • A: The minimum value of n is 3 because a star graph has 1 center and at least 2 leaves.
2. Q: Can we assume the input edges are always going to form a valid star graph?
   • A: Yes, the input edges will always form a valid star graph as per the problem constraints.
3. Q: Will the input always have at least one edge?
   • A: Yes, since the minimum n is 3, there will always be at least 2 edges.

Strategy

• A star graph has a unique center node, which is directly connected to all other nodes.
• For the given edge list, observe that the center node must be a part of every edge pairing.
• Thus, the center node must appear more frequently than any other node.
• However, in a star graph with n nodes, checking the first two edges is sufficient:
  • If the same node appears in both of these edges, it is the center node.
  • Otherwise, the common node between any two edges among the first few pairs is the center node.

Code

Here’s the Java solution to identify the center node of the star graph:

public class Solution {
    public int findCenter(int[][] edges) {
        // Extract the first two edges
        int[] edge0 = edges[0];
        int[] edge1 = edges[1];

        // Check for the common node in the first two edges
        if (edge0[0] == edge1[0] || edge0[0] == edge1[1]) {
            return edge0[0];
        } else {
            return edge0[1];
        }
    }
}

Explanation

1. Extract the first two edges edges[0] and edges[1].
2. Check for the common node:
   • If edge0[0] matches with either edge1[0] or edge1[1], this node is the center.
   • Otherwise, edge0[1] is the center since it would be the common node between first two pairs.

Time Complexity

• The time complexity of this solution is O(1) because we are only examining the first two edges to determine the center of the star graph. This constant time complexity is highly efficient for the problem constraints.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?