Minimum Degree of a Connected Trio in a Graph

Explore More Solutions

Problem Description

Welcome to the world of graphs, where connections are everything! Imagine you’re at a party, and you want to find the most popular trio of friends who are all connected. But wait! You don’t want just any trio; you want the one with the least number of connections to the outside world. Sounds like a social nightmare, right?

In the LeetCode problem “Minimum Degree of a Connected Trio in a Graph,” you are given a number of nodes (friends) and edges (connections). Your task is to find the trio of nodes that are all connected to each other and have the minimum degree (the number of connections they have). If no such trio exists, you should return -1.

So, if you’ve ever tried to find the least popular group of friends at a party, you’ll feel right at home with this problem!

Code Solution


class Solution {
 public:
  int minTrioDegree(int n, vector>& edges) {
    int ans = INT_MAX;
    vector> graph(n);
    vector degrees(n);

    for (const vector& edge : edges) {
      const int u = edge[0] - 1;
      const int v = edge[1] - 1;
      graph[min(u, v)].insert(max(u, v));
      ++degrees[u];
      ++degrees[v];
    }

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

    return ans == INT_MAX ? -1 : ans;
  }
};

Approach

The approach taken in this solution involves creating a graph representation using an adjacency list and an array to keep track of the degrees of each node. The algorithm iterates through each node and checks for pairs of connected nodes to find a trio. If a trio is found, it calculates the total degree of the trio and updates the minimum degree found so far.

Time and Space Complexity

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

Real-World Example

Imagine you’re trying to find the least popular trio in a social network. You have a list of friends and their connections. By applying the same logic as in the problem, you can identify which trio of friends has the least connections to others, making them the least popular group at the party.