Problem Description

The "Minimum Degree of a Connected Trio in a Graph" problem asks you to analyze an undirected graph with n nodes, labeled from 1 to n, and a list of undirected edges. Your goal is to find the minimum degree of any connected trio of nodes in the graph.

• A connected trio is a set of three nodes such that every pair of them is directly connected by an edge (i.e., they form a triangle).
• The degree of a trio is the total number of edges that connect any node in the trio to a node outside the trio.

You need to return the minimum degree among all connected trios in the graph. If there is no such trio, return -1.

Constraints:

• 1 ≤ n ≤ 400
• 1 ≤ edges.length ≤ n * (n - 1) / 2
• No repeated edges or self-loops

Thought Process

At first glance, the problem seems to require checking all possible trios of nodes for being connected and then calculating their degree. This brute-force approach would involve iterating over all possible combinations of three nodes, checking if all three edges exist, and then counting the external connections.

However, with n up to 400, the number of possible trios is roughly 10 million (nC3), and checking each trio naively can be inefficient. Thus, we need to optimize:

• Efficiently check if three nodes form a trio: Use adjacency matrices or sets for O(1) edge existence checks.
• Efficiently compute the degree of a trio: Precompute the degree of each node, then for a trio, sum their degrees and subtract internal edges.

The key insight is to use data structures that allow constant-time checks and precompute as much as possible to avoid repeated work.

Solution Approach

Let's break down the algorithm step by step:

1. Build the Graph:
   • Use an adjacency matrix adj where adj[i][j] is True if there is an edge between nodes i and j.
   • Compute the degree of each node in an array deg.
2. Iterate Over All Trios:
   • For each combination of three distinct nodes (i, j, k) where i < j < k:
     • Check if all three pairs are connected (adj[i][j], adj[j][k], adj[i][k]).
     • If so, they form a connected trio.
3. Compute the Degree of the Trio:
   • The degree of the trio is deg[i] + deg[j] + deg[k] - 6.
   • Why minus 6? Because each internal edge in the trio is counted twice (once for each endpoint), and there are 3 edges in the trio, so subtract 6 to remove internal connections.
4. Track the Minimum:
   • Keep a variable to track the minimum degree found.
5. Return the Result:
   • If no trio is found, return -1; otherwise, return the minimum degree.

Design Choices:

• The adjacency matrix allows O(1) checks for edge existence, making trio checks fast.
• Precomputing node degrees avoids repeated counting.
• Iterating only over i < j < k avoids duplicate trio checks.

Example Walkthrough

Sample Input:
n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]

1. Build the adjacency matrix and degree array:
   • deg[1] = 3 (edges to 2, 3, 4)
   • deg[2] = 3 (edges to 1, 3, 5)
   • deg[3] = 3 (edges to 1, 2, 6)
   • Remaining nodes have degree 1.
2. Find all trios:
   • The only trio is (1,2,3), since 1-2, 2-3, 1-3 all exist.
3. Degree of the trio (1,2,3):
   • deg[1] + deg[2] + deg[3] = 3 + 3 + 3 = 9
   • Subtract 6 for the internal edges: 9 - 6 = 3
4. Check for other trios:
   • No other set of three nodes forms a triangle.
5. Result:
   • The minimum degree is 3.

Code Implementation

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        adj = [[False] * (n + 1) for _ in range(n + 1)]
        deg = [0] * (n + 1)
        for u, v in edges:
            adj[u][v] = adj[v][u] = True
            deg[u] += 1
            deg[v] += 1

        ans = float('inf')
        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                if not adj[i][j]:
                    continue
                for k in range(j + 1, n + 1):
                    if adj[i][k] and adj[j][k]:
                        trio_deg = deg[i] + deg[j] + deg[k] - 6
                        ans = min(ans, trio_deg)
        return ans if ans != float('inf') else -1
      

class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<vector<bool>> adj(n + 1, vector<bool>(n + 1, false));
        vector<int> deg(n + 1, 0);
        for (const auto& e : edges) {
            int u = e[0], v = e[1];
            adj[u][v] = adj[v][u] = true;
            deg[u]++;
            deg[v]++;
        }
        int ans = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (!adj[i][j]) continue;
                for (int k = j + 1; k <= n; ++k) {
                    if (adj[i][k] && adj[j][k]) {
                        int trio_deg = deg[i] + deg[j] + deg[k] - 6;
                        ans = min(ans, trio_deg);
                    }
                }
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};
      

class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        boolean[][] adj = new boolean[n + 1][n + 1];
        int[] deg = new int[n + 1];
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            adj[u][v] = adj[v][u] = true;
            deg[u]++;
            deg[v]++;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (!adj[i][j]) continue;
                for (int k = j + 1; k <= n; ++k) {
                    if (adj[i][k] && adj[j][k]) {
                        int trioDeg = deg[i] + deg[j] + deg[k] - 6;
                        ans = Math.min(ans, trioDeg);
                    }
                }
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
      

var minTrioDegree = function(n, edges) {
    const adj = Array.from({length: n+1}, () => Array(n+1).fill(false));
    const deg = Array(n+1).fill(0);
    for (let [u, v] of edges) {
        adj[u][v] = adj[v][u] = true;
        deg[u]++;
        deg[v]++;
    }
    let ans = Infinity;
    for (let i = 1; i <= n; ++i) {
        for (let j = i+1; j <= n; ++j) {
            if (!adj[i][j]) continue;
            for (let k = j+1; k <= n; ++k) {
                if (adj[i][k] && adj[j][k]) {
                    let trioDeg = deg[i] + deg[j] + deg[k] - 6;
                    ans = Math.min(ans, trioDeg);
                }
            }
        }
    }
    return ans === Infinity ? -1 : ans;
};
      

Time and Space Complexity

• Brute-force approach:
  • Time: O(n³) to check all trios, plus O(1) per trio for degree calculation if degrees are precomputed.
  • Space: O(n²) for the adjacency matrix, O(n) for degree array.
• Optimized approach (as implemented):
  • Time: Still O(n³) in the worst case, but each trio check and degree calculation is O(1).
  • Space: O(n²) for adjacency matrix, O(n) for degrees.
• Why this is acceptable: For n ≤ 400, O(n³) is about 64 million iterations, which is feasible for this problem size.

Summary

To solve the "Minimum Degree of a Connected Trio in a Graph" problem, we:

• Used an adjacency matrix for fast edge existence checks.
• Precomputed node degrees for efficient degree calculation.
• Systematically checked all possible trios and tracked the minimum external degree.