Minimum Degree of a Connected Trio in a Graph solution and explanation
9 more videos on this problem
LeetCode 1761. Minimum Degree of a Connected Trio in a GraphHappy Coding · 15:19 · 2K views
LeetCode 1761. Minimum Degree of a Connected Trio in a Graph | Weekly Contest 228 | Algo ExplainedCherry Coding [IIT-G] · 14:07 · 2K views
1761. Minimum Degree of a Connected Trio in a Graph (Leetcode Hard)Programming Live with Larry · 16:38 · 844 views
【每日一题】1761. Minimum Degree of a Connected Trio in a Graph , 2/14/2021Huifeng Guan · 20:36 · 618 views
5679. Minimum Degree of a Connected Trio in a Graph | Weekly Contest 228 | Leetcode | Hindi | C++Leetforces · 12:36 · 324 views
LeetCode 1761. Minimum Degree of a Connected Trio in a Graph宰相小甘罗 · 4:49 · 220 views
Leetcode 1761. Minimum Degree of a Connected Trio in a GraphElite Code · 33:52 · 187 views
LeetCode 1761. Minimum Degree of a Connected Trio in a Graph 中文宰相小甘罗 · 5:06 · 163 views
Leetcode 1761. Minimum Degree of a Connected Trio in a Graph (graph)LetsCode · 16:49 · 147 views
Leetcode 1761. Minimum Degree of a Connected Trio in a GraphFearless Learner · 3:40 · 123 views
The 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:
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.
Approach overview
Problem 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 1: Graph Representation Using Adjacency Matrix
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.
def minTrioDegree(n, edges):
adj_matrix = [[0] * (n + 1) for _ in range(n + 1)]
degree = [0] * (n + 1)
for u, v in edges:
adj_matrix[u][v] = 1
adj_matrix[v][u] = 1
degree[u] += 1
degree[v] += 1
min_degree = float('inf')
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if adj_matrix[i][j]:
for k in range(j + 1, n + 1):
if adj_matrix[i][k] and adj_matrix[j][k]:
current_degree = degree[i] + degree[j] + degree[k] - 6
min_degree = min(min_degree, current_degree)
return min_degree if min_degree != float('inf') else -1
print(minTrioDegree(6, [[1, 2], [1, 3], [3, 2], [4, 1], [5, 2], [3, 6]]))import java.util.*;
class Solution {
public int minTrioDegree(int n, int[][] edges) {
boolean[][] adjMatrix = new boolean[n + 1][n + 1];
int[] degree = new int[n + 1];
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
adjMatrix[u][v] = adjMatrix[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++) {
if (adjMatrix[i][j]) {
for (int k = j + 1; k <= n; k++) {
if (adjMatrix[i][k] && adjMatrix[j][k]) {
int currentDegree = degree[i] + degree[j] + degree[k] - 6;
minDegree = Math.min(minDegree, currentDegree);
}
}
}
}
}
return minDegree == Integer.MAX_VALUE ? -1 : minDegree;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] edges = {{1, 2}, {1, 3}, {3, 2}, {4, 1}, {5, 2}, {3, 6}};
int n = 6;
System.out.println(sol.minTrioDegree(n, edges));
}
}#include <vector>
#include <climits>
using namespace std;
int minTrioDegree(int n, vector<vector<int>>& edges) {
vector<vector<bool>> graph(n + 1, vector<bool>(n + 1, false));
vector<int> degree(n + 1, 0);
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
graph[u][v] = graph[v][u] = true;
degree[u]++;
degree[v]++;
}
int minDegree = INT_MAX;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (graph[i][j]) {
for (int k = j + 1; k <= n; k++) {
if (graph[i][k] && graph[j][k]) {
int currentDegree = degree[i] + degree[j] + degree[k] - 6;
minDegree = min(minDegree, currentDegree);
}
}
}
}
}
return minDegree == INT_MAX ? -1 : minDegree;
}
int main() {
vector<vector<int>> edges = {{1, 2}, {1, 3}, {3, 2}, {4, 1}, {5, 2}, {3, 6}};
int n = 6;
return minTrioDegree(n, edges);
}function minTrioDegree(n, edges) {
const adjMatrix = Array.from({length: n + 1}, () => Array(n + 1).fill(false));
const degree = Array(n + 1).fill(0);
for (const [u, v] of edges) {
adjMatrix[u][v] = true;
adjMatrix[v][u] = true;
degree[u]++;
degree[v]++;
}
let minDegree = Infinity;
for (let i = 1; i <= n; i++) {
for (let j = i + 1; j <= n; j++) {
if (adjMatrix[i][j]) {
for (let k = j + 1; k <= n; k++) {
if (adjMatrix[i][k] && adjMatrix[j][k]) {
const currentDegree = degree[i] + degree[j] + degree[k] - 6;
if (currentDegree < minDegree) minDegree = currentDegree;
}
}
}
}
}
return minDegree === Infinity ? -1 : minDegree;
}
console.log(minTrioDegree(6, [[1, 2], [1, 3], [3, 2], [4, 1], [5, 2], [3, 6]]));#include <stdio.h>
#include <limits.h>
int minTrioDegree(int n, int edges[][2], int edgesSize, int edgesColSize) {
int adjMatrix[n + 1][n + 1], degree[n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++)
adjMatrix[i][j] = 0;
degree[i] = 0;
}
for (int i = 0; i < edgesSize; i++) {
int u = edges[i][0], v = edges[i][1];
adjMatrix[u][v] = adjMatrix[v][u] = 1;
degree[u]++;
degree[v]++;
}
int minDeg = INT_MAX;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (adjMatrix[i][j]) {
for (int k = j + 1; k <= n; k++) {
if (adjMatrix[i][k] && adjMatrix[j][k]) {
int currentDegree = degree[i] + degree[j] + degree[k] - 6;
if (currentDegree < minDeg) minDeg = currentDegree;
}
}
}
}
}
return minDeg == INT_MAX ? -1 : minDeg;
}
int main() {
int edges[][2] = {{1, 2}, {1, 3}, {3, 2}, {4, 1}, {5, 2}, {3, 6}};
int n = 6;
printf("%d\n", minTrioDegree(n, edges, 6, 2));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinTrioDegree(int n, int[][] edges) {
bool[,] adjMatrix = new bool[n + 1, n + 1];
int[] degree = new int[n + 1];
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
adjMatrix[u, v] = true;
adjMatrix[v, u] = true;
degree[u]++;
degree[v]++;
}
int minDegree = int.MaxValue;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (adjMatrix[i, j]) {
for (int k = j + 1; k <= n; k++) {
if (adjMatrix[i, k] && adjMatrix[j, k]) {
int currentDegree = degree[i] + degree[j] + degree[k] - 6;
minDegree = Math.Min(minDegree, currentDegree);
}
}
}
}
}
return minDegree == int.MaxValue ? -1 : minDegree;
}
public static void Main() {
var solution = new Solution();
int[][] edges = new int[][] {
new int[] { 1, 2 }, new int[] { 1, 3 }, new int[] { 3, 2 },
new int[] { 4, 1 }, new int[] { 5, 2 }, new int[] { 3, 6 }
};
Console.WriteLine(solution.MinTrioDegree(6, edges));
}
}Here, a Python solution designs an adjacency matrix in conjunction with a degree list per node, systematically checking for trio formations among nodes. Once a trio is confirmed, it subtracts in-trio edges to calculate total contributions of mostly external edges.
Time Complexity: O(n^3), iterating through triads of nodes.
Space Complexity: O(n^2) for adjacency matrix use.
Approach 2: Graph Representation Using Adjacency List with Optimized Edge Search
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.
def minTrioDegree(n, edges):
from collections import defaultdict
adj_list = defaultdict(list)
degree = [0] * (n + 1)
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)
degree[u] += 1
degree[v] += 1
for k in adj_list:
adj_list[k].sort()
min_degree = float('inf')
for u in range(1, n + 1):
for i in range(len(adj_list[u])):
for j in range(i + 1, len(adj_list[u])):
v = adj_list[u][i]
w = adj_list[u][j]
if w in adj_list[v]:
current_degree = degree[u] + degree[v] + degree[w] - 6
min_degree = min(min_degree, current_degree)
return min_degree if min_degree != float('inf') else -1
print(minTrioDegree(6, [[1, 2], [1, 3], [3, 2], [4, 1], [5, 2], [3, 6]]))import java.util.*;
class Solution {
public int minTrioDegree(int n, int[][] edges) {
List<Integer>[] adjList = new List[n + 1];
int[] degree = new int[n + 1];
for (int i = 1; i <= n; i++) {
adjList[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
adjList[u].add(v);
adjList[v].add(u);
degree[u]++;
degree[v]++;
}
for (int i = 1; i <= n; i++) {
Collections.sort(adjList[i]);
}
int minDegree = Integer.MAX_VALUE;
for (int u = 1; u <= n; u++) {
for (int i = 0; i < adjList[u].size(); i++) {
for (int j = i + 1; j < adjList[u].size(); j++) {
int v = adjList[u].get(i), w = adjList[u].get(j);
if (Collections.binarySearch(adjList[v], w) >= 0) {
int currentDegree = degree[u] + degree[v] + degree[w] - 6;
minDegree = Math.min(minDegree, currentDegree);
}
}
}
}
return minDegree == Integer.MAX_VALUE ? -1 : minDegree;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] edges = {{1, 2}, {1, 3}, {3, 2}, {4, 1}, {5, 2}, {3, 6}};
int n = 6;
System.out.println(sol.minTrioDegree(n, edges));
}
}#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int minTrioDegree(int n, vector<vector<int>>& edges) {
vector<vector<int>> adjList(n + 1);
vector<int> degree(n + 1, 0);
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
adjList[u].push_back(v);
adjList[v].push_back(u);
degree[u]++;
degree[v]++;
}
for (int i = 1; i <= n; ++i) {
sort(adjList[i].begin(), adjList[i].end());
}
int minDegree = INT_MAX;
for (int u = 1; u <= n; ++u) {
for (int i = 0; i < adjList[u].size(); ++i) {
for (int j = i + 1; j < adjList[u].size(); ++j) {
int v = adjList[u][i], w = adjList[u][j];
if (binary_search(adjList[v].begin(), adjList[v].end(), w)) {
int currentDegree = degree[u] + degree[v] + degree[w] - 6;
minDegree = min(minDegree, currentDegree);
}
}
}
}
return minDegree == INT_MAX ? -1 : minDegree;
}
int main() {
vector<vector<int>> edges = {{1, 2}, {1, 3}, {3, 2}, {4, 1}, {5, 2}, {3, 6}};
int n = 6;
return minTrioDegree(n, edges);
}function minTrioDegree(n, edges) {
const adjList = Array.from({ length: n + 1 }, () => []);
const degree = Array(n + 1).fill(0);
for (const [u, v] of edges) {
adjList[u].push(v);
adjList[v].push(u);
degree[u]++;
degree[v]++;
}
for (let i = 1; i <= n; i++) {
adjList[i].sort((a, b) => a - b);
}
let minDegree = Infinity;
for (let u = 1; u <= n; u++) {
for (let i = 0; i < adjList[u].length; i++) {
for (let j = i + 1; j < adjList[u].length; j++) {
const v = adjList[u][i];
const w = adjList[u][j];
if (adjList[v].includes(w)) {
const currentDegree = degree[u] + degree[v] + degree[w] - 6;
minDegree = Math.min(minDegree, currentDegree);
}
}
}
}
return minDegree === Infinity ? -1 : minDegree;
}
console.log(minTrioDegree(6, [[1, 2], [1, 3], [3, 2], [4, 1], [5, 2], [3, 6]]));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int minTrioDegree(int n, int edges[][2], int edgesSize, int edgesColSize) {
int *degree = (int *)calloc((n + 1), sizeof(int));
int **adjList = (int **)malloc((n + 1) * sizeof(int *));
int *adjListSize = (int *)calloc((n + 1), sizeof(int));
for (int i = 0; i <= n; i++) {
adjList[i] = (int *)malloc(400 * sizeof(int));
}
for (int i = 0; i < edgesSize; i++) {
int u = edges[i][0], v = edges[i][1];
degree[u]++;
degree[v]++;
adjList[u][adjListSize[u]++] = v;
adjList[v][adjListSize[v]++] = u;
}
int minDeg = INT_MAX;
for (int i = 1; i <= n; i++) {
qsort(adjList[i], adjListSize[i], sizeof(int), compare);
}
for (int u = 1; u <= n; u++) {
for (int j = 0; j < adjListSize[u]; j++) {
for (int k = j + 1; k < adjListSize[u]; k++) {
int v = adjList[u][j];
int w = adjList[u][k];
if (bsearch(&w, adjList[v], adjListSize[v], sizeof(int), compare) != NULL) {
minDeg = (degree[u] + degree[v] + degree[w] - 6 < minDeg) ? (degree[u] + degree[v] + degree[w] - 6) : minDeg;
}
}
}
}
for (int i = 0; i <= n; i++) {
free(adjList[i]);
}
free(adjList);
free(degree);
free(adjListSize);
return minDeg == INT_MAX ? -1 : minDeg;
}
int main() {
int edges[][2] = {{1, 2}, {1, 3}, {3, 2}, {4, 1}, {5, 2}, {3, 6}};
int n = 6;
printf("%d\n", minTrioDegree(n, edges, 6, 2));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinTrioDegree(int n, int[][] edges) {
var adjList = new List<int>[n + 1];
for (int i = 0; i <= n; i++) adjList[i] = new List<int>();
int[] degree = new int[n + 1];
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
adjList[u].Add(v);
adjList[v].Add(u);
degree[u]++;
degree[v]++;
}
for (int i = 1; i <= n; i++) {
adjList[i].Sort();
}
int minDegree = int.MaxValue;
for (int u = 1; u <= n; u++) {
for (int i = 0; i < adjList[u].Count; i++) {
for (int j = i + 1; j < adjList[u].Count; j++) {
int v = adjList[u][i];
int w = adjList[u][j];
if (adjList[v].BinarySearch(w) >= 0) {
int currentDegree = degree[u] + degree[v] + degree[w] - 6;
minDegree = Math.Min(minDegree, currentDegree);
}
}
}
}
return minDegree == int.MaxValue ? -1 : minDegree;
}
public static void Main() {
var solution = new Solution();
int[][] edges = new int[][] {
new int[] { 1, 2 }, new int[] { 1, 3 }, new int[] { 3, 2 },
new int[] { 4, 1 }, new int[] { 5, 2 }, new int[] { 3, 6 }
};
Console.WriteLine(solution.MinTrioDegree(6, edges));
}
}This Python-based solution makes use of a mapped adjacency list, improved by sorting for binary edge verification, effectively calculating the trio degrees and updating the minimal value encountered as the script progresses over potential trios.
Time Complexity: O(n * d log d) with n node operations and sorted list searches.
Space Complexity: O(n + m) managing node to adjacency correlativity.
Approach 3: Brute Force Enumeration
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.
function minTrioDegree(n: number, edges: number[][]): number {
const g = Array.from({ length: n }, () => Array(n).fill(false));
const deg: number[] = Array(n).fill(0);
for (let [u, v] of edges) {
u--;
v--;
g[u][v] = g[v][u] = true;
++deg[u];
++deg[v];
}
let ans = Infinity;
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
if (g[i][j]) {
for (let 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 === Infinity ? -1 : ans;
}func minTrioDegree(n int, edges [][]int) int {
g := make([][]bool, n)
deg := make([]int, n)
for i := range g {
g[i] = make([]bool, n)
}
for _, e := range edges {
u, v := e[0]-1, e[1]-1
g[u][v], g[v][u] = true, true
deg[u]++
deg[v]++
}
ans := 1 << 30
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if g[i][j] {
for k := j + 1; k < n; k++ {
if g[i][k] && g[j][k] {
ans = min(ans, deg[i]+deg[j]+deg[k]-6)
}
}
}
}
}
if ans == 1<<30 {
return -1
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Graph Representation Using Adjacency Matrix | Time Complexity: O(n^3), iterating through triads of nodes. |
| Graph Representation Using Adjacency List with Optimized Edge Search | Time Complexity: O(n * d log d) with n node operations and sorted list searches. |
| Brute Force Enumeration | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Degree of a Connected Trio in a Graph easy or hard?
Minimum Degree of a Connected Trio in a Graph is classified as a Hard problem. The challenge comes from efficiently detecting triangles in a graph while correctly computing the trio degree and avoiding duplicate counting.
Minimum Degree of a Connected Trio in a Graph Python/Java solution
Python and Java solutions typically build an adjacency list and maintain node degree counts. The algorithm iterates through edges, finds a third node connected to both endpoints, and computes the trio degree using deg[u] + deg[v] + deg[w] - 6. The same logic works across Python, Java, C++, and other languages.
How to solve Minimum Degree of a Connected Trio in a Graph in O(n)?
Solving it strictly in O(n) is not feasible because you must inspect edges to detect triangles. The practical optimized approach uses adjacency lists and checks common neighbors of edge endpoints. This typically runs around O(m * d), which is efficient for sparse graphs where node degrees are small.
What is the best approach for Minimum Degree of a Connected Trio in a Graph?
The most efficient approach iterates over edges and searches for a third node that forms a triangle with the edge's endpoints. Using an adjacency list with fast edge lookup allows you to detect connected trios and compute the degree using deg[u] + deg[v] + deg[w] - 6. This reduces unnecessary triple checks and typically runs in about O(m * d) time where d is the average degree.
Is Minimum Degree of a Connected Trio in a Graph asked at Google/Amazon/Meta?
Triangle detection and graph degree analysis appear frequently in graph interview questions at large companies including Google, Amazon, and Meta. This problem specifically tests triangle detection, graph representation choices, and efficient edge traversal patterns.
What data structure is used in Minimum Degree of a Connected Trio in a Graph?
The problem relies on graph data structures such as adjacency matrices or adjacency lists. Node degrees are tracked with arrays, and many optimized implementations also use hash sets or boolean matrices to check whether an edge exists in constant time.
What is the time complexity of Minimum Degree of a Connected Trio in a Graph?
A brute-force solution using an adjacency matrix checks all node triples and runs in O(n^3) time. The optimized solution iterates through edges and searches for a common neighbor, giving roughly O(m * d) time complexity with O(n + m) space, which performs much better for sparse graphs.