Scale Engineer

Minimum Degree of a Connected Trio in a Graph

Hard
#1612Time: 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.
Data structures
Graph

Prompt

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 <= 400
  • edges[i].length == 2
  • 1 <= edges.length <= n * (n-1) / 2
  • 1 <= ui, vi <= n
  • ui != 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 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.

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).

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem