Minimum Degree of a Connected Trio in a Graph
HardPrompt
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 != vi- There are no repeated edges.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create an adjacency matrix
adjfor O(1) edge lookups and adegreesarray to store the degree of each node. - Initialize
min_degreetoInteger.MAX_VALUE. - Use three nested loops to iterate through all unique triplets of nodes
(i, j, k)where1 <= 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_degreewith the minimum degree found. - If
min_degreewas never updated, no trios exist; return -1. Otherwise, returnmin_degree.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Build an adjacency matrix
adjand adegreesarray from the inputedges. - Initialize
min_degreetoInteger.MAX_VALUE. - Iterate through each edge
(u, v)in the graph. - For each edge, start a third loop to iterate through all other nodes
wfrom1ton. - Inside the loop, check if
wis connected to bothuandvusing the adjacency matrix. - If
wforms a trio{u, v, w}, calculate its degree:degrees[u] + degrees[v] + degrees[w] - 6. - Update
min_degreewith the minimum degree found. - Return
min_degreeif a trio was found, otherwise return -1.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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
Eis close ton^2, the complexity approaches O(n^3), offering little improvement over the brute-force method.
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.
Algorithm
- Pre-computation: Build an adjacency matrix
adjMatrixfor O(1) lookups, an adjacency listadjListfor iterating neighbors, and adegreearray. - Initialize
min_degreetoInteger.MAX_VALUE. - Iterate through each node
ifrom1ton. - For each neighbor
jofi(fromadjList[i]) such thati < j: - For each neighbor
kofi(fromadjList[i]) such thatj < k: - Check if
jandkare connected usingadjMatrix[j][k]. - If they are connected, a trio
{i, j, k}is found. - Calculate its degree
degree[i] + degree[j] + degree[k] - 6and updatemin_degree. - Return
min_degreeif a trio was found, otherwise -1.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.