# Minimum Degree of a Connected Trio in a Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-degree-of-a-connected-trio-in-a-graph)
Canonical: https://scaleengineer.com/dsa/problems/minimum-degree-of-a-connected-trio-in-a-graph
**Data structures:** Graph
---
## Problem
You are given an undirected graph. You are given an integer `n` which is the number of nodes in the graph and an array `edges`, where each `edges[i] = [ui, vi]` indicates that there is an undirected edge between `ui` and `vi`.

A **connected trio** is a set of **three** nodes where there is an edge between **every** pair of them.

The **degree of a connected trio** is the number of edges where one endpoint is in the trio, and the other is not.

Return _the **minimum** degree of a connected trio in the graph, or_ `-1` _if the graph has no connected trios._

**Example 1:**

![](https://assets.glich.co/dsa/minimum-degree-of-a-connected-trio-in-a-graph/image0.png) 

**Input:** n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
**Output:** 3
**Explanation:** There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-degree-of-a-connected-trio-in-a-graph/image1.png) 

**Input:** n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
**Output:** 0
**Explanation:** There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

**Constraints:**

* `2 <= n <= 400`
* `edges[i].length == 2`
* `1 <= edges.length <= n * (n-1) / 2`
* `1 <= ui, vi <= n`
* `ui != vi`
* There are no repeated edges.

# Approaches
## Brute-Force by Node Triplets
This is the most straightforward but also the least efficient approach. It involves checking every possible combination of three distinct nodes in the graph to see if they form a connected trio (a triangle). If a trio is found, its degree is calculated, and we keep track of the minimum degree seen so far.
**Time:** O(n^3) - The three nested loops to iterate through all possible triplets of nodes dominate the runtime. Pre-computation takes O(E + n^2), which is absorbed by O(n^3). · **Space:** O(n^2) - Required for the adjacency matrix to store graph connectivity. The degree array takes an additional O(n) space.
**Pros:** Simple to conceptualize and implement.
**Cons:** Highly inefficient due to its cubic time complexity.; Likely to result in a 'Time Limit Exceeded' (TLE) error for larger values of `n` (e.g., `n=400`).
### Explanation
The algorithm begins by pre-processing the graph data. We build an adjacency matrix for constant-time edge existence checks and an array to store the degree of each node. Then, we systematically iterate through every unique triplet of nodes `(i, j, k)`. For each triplet, we verify if it's a connected trio by checking for the presence of all three edges: `(i, j)`, `(j, k)`, and `(i, k)`. If it is a trio, we compute its degree using the pre-calculated node degrees with the formula `degree(i) + degree(j) + degree(k) - 6`. This formula works because the sum of the degrees of the three nodes counts the internal trio edges twice, and there are 3 internal edges, so we subtract `3 * 2 = 6`. We maintain a variable, `min_degree`, initialized to infinity, and update it whenever a smaller trio degree is found. Finally, we return `min_degree`, or -1 if no trios were found.

```java
class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        boolean[][] adj = new boolean[n + 1][n + 1];
        int[] degree = new int[n + 1];
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u][v] = true;
            adj[v][u] = true;
            degree[u]++;
            degree[v]++;
        }

        int minDegree = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                for (int k = j + 1; k <= n; k++) {
                    if (adj[i][j] && adj[j][k] && adj[k][i]) {
                        // Found a trio {i, j, k}
                        int currentDegree = degree[i] + degree[j] + degree[k] - 6;
                        minDegree = Math.min(minDegree, currentDegree);
                    }
                }
            }
        }

        return minDegree == Integer.MAX_VALUE ? -1 : minDegree;
    }
}
```
### Algorithm
*   Create an adjacency matrix `adj` for O(1) edge lookups and a `degrees` array to store the degree of each node.
*   Initialize `min_degree` to `Integer.MAX_VALUE`.
*   Use three nested loops to iterate through all unique triplets of nodes `(i, j, k)` where `1 <= i < j < k <= n`.
*   For each triplet, use the adjacency matrix to check if edges `(i, j)`, `(j, k)`, and `(i, k)` all exist.
*   If they form a trio, calculate its degree: `degrees[i] + degrees[j] + degrees[k] - 6`.
*   Update `min_degree` with the minimum degree found.
*   If `min_degree` was never updated, no trios exist; return -1. Otherwise, return `min_degree`.

## Edge-Based Trio Search
This approach improves upon the brute-force method by changing the search strategy. Instead of iterating through all possible node triplets, we iterate through each existing edge `(u, v)`. For each edge, we then search for a third node `w` that is a common neighbor to both `u` and `v`, which would complete the trio.
**Time:** O(E * n) - Where `E` is the number of edges and `n` is the number of nodes. We iterate through `E` edges, and for each, we scan up to `n` nodes. · **Space:** O(n^2) - For the adjacency matrix.
**Pros:** More efficient than the O(n^3) brute-force approach, especially for sparse graphs.; Relatively easy to implement.
**Cons:** For dense graphs where the number of edges `E` is close to `n^2`, the complexity approaches O(n^3), offering little improvement over the brute-force method.
### Explanation
The core idea is that any trio must contain three edges. By starting our search from an existing edge `(u, v)`, we only need to find one more node `w` that connects to both `u` and `v`. The algorithm first pre-computes an adjacency matrix and node degrees. Then, it iterates through every edge in the input list. For each edge `(u, v)`, it performs a linear scan through all `n` nodes of the graph. If a node `k` is found such that `(u, k)` and `(v, k)` are both edges, a trio `{u, v, k}` has been identified. Its degree is calculated and compared with the current minimum. This method is more efficient than the pure brute-force approach for sparse graphs because it avoids checking pairs of nodes that aren't even connected by an edge.

```java
class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        boolean[][] adj = new boolean[n + 1][n + 1];
        int[] degree = new int[n + 1];
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u][v] = true;
            adj[v][u] = true;
            degree[u]++;
            degree[v]++;
        }

        int minDegree = Integer.MAX_VALUE;

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            for (int k = 1; k <= n; k++) {
                if (k != u && k != v) {
                    if (adj[u][k] && adj[v][k]) {
                        // Found a trio {u, v, k}
                        int currentDegree = degree[u] + degree[v] + degree[k] - 6;
                        minDegree = Math.min(minDegree, currentDegree);
                    }
                }
            }
        }

        return minDegree == Integer.MAX_VALUE ? -1 : minDegree;
    }
}
```
### Algorithm
*   Build an adjacency matrix `adj` and a `degrees` array from the input `edges`.
*   Initialize `min_degree` to `Integer.MAX_VALUE`.
*   Iterate through each edge `(u, v)` in the graph.
*   For each edge, start a third loop to iterate through all other nodes `w` from `1` to `n`.
*   Inside the loop, check if `w` is connected to both `u` and `v` using the adjacency matrix.
*   If `w` forms a trio `{u, v, w}`, calculate its degree: `degrees[u] + degrees[v] + degrees[w] - 6`.
*   Update `min_degree` with the minimum degree found.
*   Return `min_degree` if a trio was found, otherwise return -1.

## Optimized Trio Search by Finding Triangles
This is the most efficient approach, which optimizes the search for trios. Instead of a generic search, it leverages the graph's structure. For each node `i`, it considers pairs of its neighbors, `j` and `k`. If `j` and `k` are also connected, then `{i, j, k}` forms a trio. This method effectively counts all triangles in the graph.
**Time:** O(Σ(degree(i)^2)) which is bounded by O(E^1.5) in many cases. This is significantly faster than O(E*n) for non-dense graphs. · **Space:** O(n^2) - Requires both an adjacency matrix and an adjacency list.
**Pros:** The most time-efficient approach, with a complexity generally better than O(E*n).; Guaranteed to pass within typical time limits for the given constraints.
**Cons:** The implementation is slightly more complex, requiring both an adjacency matrix and an adjacency list for optimal performance.; The space complexity remains O(n^2).
### Explanation
This optimized algorithm relies on a combination of data structures for efficiency. We use an adjacency list to quickly iterate through the neighbors of a node and an adjacency matrix for constant-time checks of an edge between any two neighbors. The algorithm iterates through each node `i`. For each `i`, it iterates through all pairs of its neighbors, `j` and `k`. By enforcing an order (e.g., `i < j < k`), we can ensure each trio is considered exactly once. For each such pair of neighbors, we check if an edge exists between `j` and `k`. If it does, we have found a trio. The time complexity of this method is `O(sum(degree(i)^2))` over all nodes `i`, which is bounded by `O(E * alpha)` where `alpha` is the graph's arboricity, and more generally by `O(E^1.5)`. This is significantly faster than the previous approaches for most graphs.

```java
class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        boolean[][] adjMatrix = new boolean[n + 1][n + 1];
        List<List<Integer>> adjList = new ArrayList<>();
        int[] degree = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            // Ensure u < v to simplify loops later, though not strictly necessary
            int u = Math.min(edge[0], edge[1]);
            int v = Math.max(edge[0], edge[1]);
            adjMatrix[u][v] = adjMatrix[v][u] = true;
            adjList.get(u).add(v);
            adjList.get(v).add(u);
            degree[u]++;
            degree[v]++;
        }

        int minDegree = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            List<Integer> neighbors = adjList.get(i);
            for (int neighbor_idx1 = 0; neighbor_idx1 < neighbors.size(); neighbor_idx1++) {
                for (int neighbor_idx2 = neighbor_idx1 + 1; neighbor_idx2 < neighbors.size(); neighbor_idx2++) {
                    int j = neighbors.get(neighbor_idx1);
                    int k = neighbors.get(neighbor_idx2);
                    
                    // We have edges (i,j) and (i,k). Check for (j,k).
                    if (adjMatrix[j][k]) {
                        int currentDegree = degree[i] + degree[j] + degree[k] - 6;
                        minDegree = Math.min(minDegree, currentDegree);
                    }
                }
            }
        }

        return minDegree == Integer.MAX_VALUE ? -1 : minDegree;
    }
}
```
### Algorithm
*   Pre-computation: Build an adjacency matrix `adjMatrix` for O(1) lookups, an adjacency list `adjList` for iterating neighbors, and a `degree` array.
*   Initialize `min_degree` to `Integer.MAX_VALUE`.
*   Iterate through each node `i` from `1` to `n`.
*   For each neighbor `j` of `i` (from `adjList[i]`) such that `i < j`:
*   For each neighbor `k` of `i` (from `adjList[i]`) such that `j < k`:
*   Check if `j` and `k` are connected using `adjMatrix[j][k]`.
*   If they are connected, a trio `{i, j, k}` is found.
*   Calculate its degree `degree[i] + degree[j] + degree[k] - 6` and update `min_degree`.
*   Return `min_degree` if a trio was found, otherwise -1.

# Solutions
### Java

```java
class Solution {
public
  int minTrioDegree(int n, int[][] edges) {
    boolean[][] g = new boolean[n][n];
    int[] deg = new int[n];
    for (var e : edges) {
      int u = e[0] - 1, v = e[1] - 1;
      g[u][v] = true;
      g[v][u] = true;
      ++deg[u];
      ++deg[v];
    }
    int ans = 1 << 30;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (g[i][j]) {
          for (int k = j + 1; k < n; ++k) {
            if (g[i][k] && g[j][k]) {
              ans = Math.min(ans, deg[i] + deg[j] + deg[k] - 6);
            }
          }
        }
      }
    }
    return ans == 1 << 30 ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minTrioDegree(int n, vector<vector<int>> &edges) {
    bool g[n][n];
    memset(g, 0, sizeof g);
    int deg[n];
    memset(deg, 0, sizeof deg);
    for (auto &e : edges) {
      int u = e[0] - 1, v = e[1] - 1;
      g[u][v] = g[v][u] = true;
      deg[u]++, deg[v]++;
    }
    int ans = INT_MAX;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (g[i][j]) {
          for (int k = j + 1; k < n; ++k) {
            if (g[j][k] && g[i][k]) {
              ans = min(ans, deg[i] + deg[j] + deg[k] - 6);
            }
          }
        }
      }
    }
    return ans == INT_MAX ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int: g = [[False] * n for _ in range(n)] deg = [0] * n for u, v in edges: u, v = u - 1, v - 1 g[u][v] = g[v][u] = True deg[u] += 1 deg[v] += 1 ans = inf for i in range(n): for j in range(i + 1, n): if g[i][j]: for k in range(j + 1, n): if g[i][k] and g[j][k]: ans = min(ans, deg[i] + deg[j] + deg[k] - 6) return - 1 if ans == inf else ans

```