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.
This approach uses an adjacency matrix to store edges and checks all possible triangles that can be formed by vertices. The adjacency matrix allows efficient querying of whether an edge exists between two nodes. When a connected trio (triangle) is found, the degree is calculated by considering all edges attached to the trio nodes that go beyond the trio itself.
This C solution uses an adjacency matrix to record connected pairs of nodes and calculates the degree of each node. By iterating over all possible triplet combinations, it discovers triangles and computes the exterior degree by summing the node degrees and subtracting 6 (since each triangle has 3 internal edges).
Time Complexity: O(n^3) due to iterating through all possible triplets of nodes.
Space Complexity: O(n^2) for the adjacency matrix.
This approach makes use of an adjacency list to manage the graph's edges, enhancing triangle verification by iterating through node connections directly. This method seeks to reduce unnecessary computations by focusing only where potential trios form and storing results efficiently.
This C solution utilizes an adjacency list to store connected nodes per node. Sorting the adjacency list for each node allows binary search application to efficiently verify trio presence, where edge degree is dynamically reassessed to keep the minimum outwardly pointing edges.
Time Complexity: O(m * d log d), with m as edge count and d as max adjacencies per node.
Space Complexity: O(n + m) for adjacency lists handling.
We first store all edges in the adjacency matrix g, and then store the degree of each node in the array deg. Initialize the answer ans = +infty.
Then enumerate all triplets (i, j, k), where i \lt j \lt k. If g[i][j] = g[j][k] = g[i][k] = 1, it means these three nodes form a connected trio. In this case, update the answer to ans = min(ans, deg[i] + deg[j] + deg[k] - 6).
After enumerating all triplets, if the answer is still +infty, it means there is no connected trio in the graph, return -1. Otherwise, return the answer.
The time complexity is O(n^3), and the space complexity is O(n^2). Here, n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Graph Representation Using Adjacency Matrix | Time Complexity: O(n^3) due to iterating through all possible triplets of nodes. |
| Graph Representation Using Adjacency List with Optimized Edge Search | Time Complexity: O(m * d log d), with m as edge count and d as max adjacencies per node. |
| Brute Force Enumeration | — |
| 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 |
LeetCode 1761. Minimum Degree of a Connected Trio in a Graph • Happy Coding • 2,927 views views
Watch 9 more video solutions →Practice Minimum Degree of a Connected Trio in a Graph with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor