Watch 10 video solutions for Minimum Degree of a Connected Trio in a Graph, a hard level problem involving Graph. This walkthrough by Happy Coding has 2,927 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
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 <= 400edges[i].length == 21 <= edges.length <= n * (n-1) / 21 <= ui, vi <= nui != viProblem Overview: Given an undirected graph, you need to find a connected trio: three nodes where every pair of nodes has an edge between them. For each such trio, compute its degree, defined as the total number of edges connected to the trio's nodes but not part of the trio itself. The task is to return the minimum degree among all trios, or -1 if none exist.
Approach 1: Graph Representation Using Adjacency Matrix (O(n^3) time, O(n^2) space)
Store the graph in an adjacency matrix so you can check whether an edge exists between two nodes in constant time. Iterate through all possible node triples (i, j, k) with i < j < k. If matrix[i][j], matrix[j][k], and matrix[i][k] are all true, the three nodes form a connected trio. Precompute the degree of each node while building the graph, then calculate the trio degree using deg[i] + deg[j] + deg[k] - 6 (subtracting the internal edges counted twice). This brute-force enumeration guarantees correctness and is straightforward to implement using a graph adjacency matrix, but the O(n^3) iteration becomes expensive for large graphs.
Approach 2: Adjacency List with Optimized Edge Search (O(m * d) time, O(n + m) space)
Represent the graph using an adjacency list and maintain a fast edge lookup (typically a hash set or boolean matrix for quick checks). Instead of iterating over every triple, iterate through each edge (u, v). For that edge, search for a common neighbor w that connects to both u and v. When such a node exists, (u, v, w) forms a connected trio. To avoid duplicates, enforce an ordering constraint like u < v < w. The trio degree is computed using the same formula: deg[u] + deg[v] + deg[w] - 6. This method reduces unnecessary triple checks and leverages adjacency list traversal from a graph combined with efficient neighbor lookups, often implemented with hash-based edge checks. The runtime becomes proportional to the number of edges and local node degrees rather than all node triples.
Recommended for interviews: Interviewers typically expect the adjacency list edge-based approach. The adjacency matrix version demonstrates the core idea of detecting trios and computing degrees, but the optimized approach shows stronger graph intuition and better complexity control. Recognizing that every trio must contain an edge and then searching for a third common neighbor reduces the search space significantly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Adjacency Matrix Trio Enumeration | O(n^3) | O(n^2) | Small graphs where constant-time edge lookup simplifies implementation |
| Adjacency List with Optimized Edge Search | O(m * d) | O(n + m) | Large sparse graphs where iterating edges is far cheaper than checking all triples |