Find Center of Star Graph

Easy Graphs Degree Counting Original on LeetCode

Reported atNetflix

Find Center of Star Graph is a easy graphs problem solved with the degree counting pattern. The best approach, optimal (shared node of two edges), runs in O(1) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count degrees) up.

Problem

An undirected star graph has n nodes labelled 1 to n: one node, the center, is joined by an edge to each of the other n - 1 nodes, and there are no other edges.

You are given the list edges, where edges[i] = [u, v] is an edge between u and v. Return the label of the center.

Examples

Example 1

Input
edges = [[4, 2], [1, 2], [2, 3]]
Output
2
Why
Node 2 appears in every edge; nodes 1, 3 and 4 are leaves.

Example 2

Input
edges = [[5, 1], [5, 3], [2, 5], [5, 4]]
Output
5
Why
Every edge touches node 5, no matter which side it is written on.

Constraints

  • 3 <= n <= 10^5
  • edges.length == n - 1, and edges[i] = [u, v] with 1 <= u, v <= n, u != v
  • The edges are guaranteed to form a star graph.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (count degrees)O(n)O(n)
Optimal (shared node of two edges)O(1)O(1)

1Brute force (count degrees)

TimeO(n)One pass over the edges and one over the nodes.
SpaceO(n)The degree array.

Count how many edges touch each node. The center is the node whose degree equals the number of edges.

  1. n = edges.length + 1; create a degree array of size n + 1.
  2. For each edge [u, v], increment degree[u] and degree[v].
  3. Return the node with degree n - 1.
class Solution {
    public int findCenter(int[][] edges) {
        int n = edges.length + 1;
        int[] degree = new int[n + 1];
        for (int[] e : edges) {
            degree[e[0]]++;
            degree[e[1]]++;
        }
        for (int v = 1; v <= n; v++) {
            if (degree[v] == n - 1) return v;
        }
        return -1;
    }
}

2Optimal (shared node of two edges)

TimeO(1)Only four numbers are compared.
SpaceO(1)No extra storage.

Since every edge contains the center and the leaves are all different, the first two edges share exactly one node, and that node is the center. Check whether the first endpoint of edge 0 appears in edge 1; if not, the second endpoint must.

  1. Let [a, b] = edges[0] and [c, d] = edges[1].
  2. If a == c or a == d, return a; otherwise return b.
class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b = edges[0][1];
        return (a == edges[1][0] || a == edges[1][1]) ? a : b;
    }
}

Edge cases to test

  • The smallest star, with three nodes and two edges
  • The center is listed second in some edges and first in others
  • The center has the largest or the smallest label

Hints

Hint 1

The center has degree n - 1 and every other node has degree 1. Counting degrees works, but you can do much less.

Hint 2

The center belongs to every edge, so it is the one node shared by the first two edges.

FAQ

What is the best time complexity for Find Center of Star Graph?

Optimal (shared node of two edges) runs in O(1) time and O(1) extra space. Only four numbers are compared.

Which pattern does Find Center of Star Graph use?

It is a graphs problem that uses the degree counting pattern. Other problems with the same pattern: Minimum Number of Vertices to Reach All Nodes.

Is there a brute force solution for Find Center of Star Graph?

Yes. Brute force (count degrees) takes O(n) time and O(n) space. Count how many edges touch each node.

Which edge cases should I test for Find Center of Star Graph?

The smallest star, with three nodes and two edges; The center is listed second in some edges and first in others; The center has the largest or the smallest label.