Skip to main content
Talentd

Minimum Degree of a Connected Trio in a Graph - Solution & Explanation

HardGraph23 min readAsked at: Amazon, GoDaddy
Practice this problem

Problem Statement

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.

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.

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

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) due to iterating through all possible triplets of nodes.
Space Complexity: O(n^2) for the adjacency matrix.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Graph Representation Using Adjacency Matrix

Time Complexity: O(n^3) due to iterating through all possible triplets of nodes.
Space Complexity: O(n^2) for the adjacency matrix.

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.
Space Complexity: O(n + m) for adjacency lists handling.

Brute Force Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Adjacency Matrix Trio EnumerationO(n^3)O(n^2)Small graphs where constant-time edge lookup simplifies implementation
Adjacency List with Optimized Edge SearchO(m * d)O(n + m)Large sparse graphs where iterating edges is far cheaper than checking all triples

Video Solution

LeetCode 1761. Minimum Degree of a Connected Trio in a Graph • Happy Coding • 2,952 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Degree of a Connected Trio in a Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Edges to Make Degrees of All Nodes Even