Minimum Degree of a Connected Trio in a Graph

Explore Other Solutions

Problem Statement

Imagine you’re at a party, and you want to find the three people who know each other the best. This problem is about finding a trio of friends (nodes) in a graph where each person is connected to the others, and they have the minimum total degree (the number of friends each person has). If you can’t find such a trio, it’s time to go home and cry into your pillow.

Code Solution


class Solution {
  public int minTrioDegree(int n, int[][] edges) {
    int ans = Integer.MAX_VALUE;
    Set[] graph = new Set[n];
    int[] degrees = new int[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new HashSet<>();

    for (int[] edge : edges) {
      final int u = edge[0] - 1;
      final int v = edge[1] - 1;
      graph[Math.min(u, v)].add(Math.max(u, v));
      ++degrees[u];
      ++degrees[v];
    }

    for (int u = 0; u < n; u++)
      for (final int v : graph[u])
        for (final int w : graph[u])
          if (graph[v].contains(w))
            ans = Math.min(ans, degrees[u] + degrees[v] + degrees[w] - 6);

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}

Approach Explanation

The code initializes a graph and an array to keep track of the degrees of each node. It populates the graph with edges and counts the degrees of each node. The main logic checks each node and its connections to find all possible trios. If a trio is found, it calculates the total degree and updates the answer if this trio has a lower degree than previously found trios.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²)
Space Complexity	O(n)

Real-World Example

Imagine you're trying to form a band with your friends. You want to pick three musicians who not only know each other but also have a decent number of followers on social media. You're looking for the trio with the most connections to ensure your band has a good reach.