LeetCode Problem 1761

Difficulty: 🔴 Hard
Topics: Graph Theory, Enumeration

Solution

LeetCode 1761 - Minimum Degree of a Connected Trio in a Graph

Problem Understanding

This problem gives us an undirected graph with n nodes and a list of edges. A connected trio is a group of exactly three distinct nodes where every pair of nodes has an edge between them. In graph theory terms, this is simply a triangle.

The problem asks us to find the minimum degree among all connected trios in the graph.

The degree of a trio is not the same as the standard graph node degree. Instead, it represents the number of edges that connect nodes inside the trio to nodes outside the trio.

Suppose we have a trio (a, b, c). Each node has its own graph degree:

• degree[a]
• degree[b]
• degree[c]

If we add these together, the three internal trio edges are counted twice because the graph is undirected:

• edge (a, b)
• edge (a, c)
• edge (b, c)

Each of these contributes two counts to the total degree sum, so the internal trio edges contribute 6 total counts.

Therefore, the degree of the trio is:

$\text{trio degree} = degree[a] + degree[b] + degree[c] - 6$

The input consists of:

• n, the number of nodes labeled from 1 to n
• edges, where each edge connects two nodes

The output should be:

• the minimum trio degree among all valid connected trios
• -1 if the graph contains no connected trio at all

The constraints are important:

• n <= 400
• The graph can be dense, potentially containing nearly every possible edge

Since n is only 400, an O(n^3) solution is acceptable because:

$400^3 = 64,000,000$

This is large but still manageable in optimized implementations.

Several edge cases matter:

• The graph may contain no triangles at all
• The graph may contain many overlapping trios
• Some trios may have degree 0, meaning no external connections
• Dense graphs can produce many candidate trios, so repeated expensive adjacency checks can become problematic
• Because the graph is undirected, adjacency representation must support symmetric lookups

The problem guarantees:

• No duplicate edges
• No self loops
• Valid node indices

These guarantees simplify the implementation significantly.

Approaches

Brute Force Approach

The most direct solution is to enumerate every possible set of three nodes and check whether they form a connected trio.

For every triple (a, b, c):

1. Check whether:

• (a, b) exists
• (a, c) exists
• (b, c) exists

2. If all three edges exist, compute the trio degree.

To compute the trio degree naively, we could scan every edge and count how many edges connect the trio to outside nodes.

This approach is correct because it explicitly checks every possible trio and computes its exact degree. However, it becomes inefficient because:

• There are O(n^3) possible triples
• Degree computation could take O(E) time per trio

This leads to:

$O(n^3 \cdot E)$

In dense graphs where:

$E = O(n^2)$

the total complexity becomes:

$O(n^5)$

which is far too slow.

Optimal Approach

The key observation is that once we know three nodes form a trio, we can compute the trio degree immediately using node degrees.

If nodes (a, b, c) form a triangle:

• each node contributes all of its incident edges
• the trio's internal edges are counted twice
• there are exactly 3 internal edges

So we subtract 6 from the total degree sum.

This eliminates the expensive edge scanning step.

We also use an adjacency matrix or adjacency set for constant time edge existence checks.

The resulting algorithm:

1. Build adjacency representation
2. Compute degree of every node
3. Enumerate triples (a, b, c)
4. Check whether they form a triangle
5. Compute:

degree[a] + degree[b] + degree[c] - 6 6. Track the minimum

This reduces complexity to:

$O(n^3)$

which is acceptable for n <= 400.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3 * E)	O(E)	Enumerates all triples and rescans edges
Optimal	O(n^3)	O(n^2)	Uses adjacency matrix and degree counting

Algorithm Walkthrough

Step 1: Build the adjacency matrix

Create a 2D boolean matrix connected where:

• connected[u][v] = True
• connected[v][u] = True

This allows constant time edge existence checks.

We choose an adjacency matrix because:

• n is small enough, only 400
• edge lookup speed is critical
• O(1) adjacency checks are faster than searching adjacency lists

Step 2: Compute node degrees

Create an array degree.

For every edge (u, v):

• increment degree[u]
• increment degree[v]

This stores the total number of incident edges for every node.

Step 3: Enumerate all possible trios

Use three nested loops:

1. a from 1 to n
2. b from a + 1 to n
3. c from b + 1 to n

This guarantees every unordered triple is processed exactly once.

Step 4: Check whether the triple forms a trio

A valid trio requires all three pairwise edges:

• (a, b)
• (a, c)
• (b, c)

So check:

connected[a][b] and connected[a][c] and connected[b][c]

If any edge is missing, skip the triple.

Step 5: Compute the trio degree

For a valid trio:

trio_degree = degree[a] + degree[b] + degree[c] - 6

We subtract 6 because:

• each internal edge contributes two degree counts
• there are three internal edges

Step 6: Track the minimum answer

Maintain a variable minimum_degree.

Update it whenever a smaller trio degree is found.

Step 7: Return the result

If no trio was found, return -1.

Otherwise return the minimum degree.

Why it works

The algorithm checks every possible trio exactly once, so no valid connected trio can be missed.

The adjacency matrix guarantees accurate detection of whether three nodes form a complete triangle.

The trio degree formula is correct because node degrees count all incident edges, including internal trio edges. Since the three internal edges are counted twice in total, subtracting 6 removes those internal contributions and leaves only edges connecting the trio to outside nodes.

Therefore, the algorithm always computes the correct minimum trio degree.

Python Solution

from typing import List

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        connected = [[False] * (n + 1) for _ in range(n + 1)]
        degree = [0] * (n + 1)

        for u, v in edges:
            connected[u][v] = True
            connected[v][u] = True

            degree[u] += 1
            degree[v] += 1

        minimum_degree = float("inf")

        for a in range(1, n + 1):
            for b in range(a + 1, n + 1):
                if not connected[a][b]:
                    continue

                for c in range(b + 1, n + 1):
                    if (
                        connected[a][c]
                        and connected[b][c]
                    ):
                        trio_degree = (
                            degree[a]
                            + degree[b]
                            + degree[c]
                            - 6
                        )

                        minimum_degree = min(
                            minimum_degree,
                            trio_degree
                        )

        return -1 if minimum_degree == float("inf") else minimum_degree

The implementation starts by constructing the adjacency matrix and computing node degrees simultaneously. Each undirected edge updates both directions in the matrix and increments both endpoint degrees.

The triple nested loops enumerate all unique node triples. The optimization:

if not connected[a][b]:
    continue

avoids unnecessary checks for many invalid triples early.

Once a valid trio is identified, the degree formula is applied immediately. The algorithm continuously tracks the smallest trio degree encountered.

Finally, if no trio exists, the answer remains infinity, and the function returns -1.

Go Solution

func minTrioDegree(n int, edges [][]int) int {
    connected := make([][]bool, n+1)
    for i := range connected {
        connected[i] = make([]bool, n+1)
    }

    degree := make([]int, n+1)

    for _, edge := range edges {
        u := edge[0]
        v := edge[1]

        connected[u][v] = true
        connected[v][u] = true

        degree[u]++
        degree[v]++
    }

    const INF = int(1e9)
    minimumDegree := INF

    for a := 1; a <= n; a++ {
        for b := a + 1; b <= n; b++ {
            if !connected[a][b] {
                continue
            }

            for c := b + 1; c <= n; c++ {
                if connected[a][c] && connected[b][c] {
                    trioDegree := degree[a] + degree[b] + degree[c] - 6

                    if trioDegree < minimumDegree {
                        minimumDegree = trioDegree
                    }
                }
            }
        }
    }

    if minimumDegree == INF {
        return -1
    }

    return minimumDegree
}

The Go implementation mirrors the Python logic closely.

Go uses slices for both the adjacency matrix and degree array. Since Go does not provide an infinity constant for integers, a large sentinel value INF is used instead.

Because all computations remain well within integer limits for n <= 400, integer overflow is not a concern.

Worked Examples

Example 1

n = 6
edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]

Step 1: Build degree array

Node	Degree
1	3
2	3
3	3
4	1
5	1
6	1

Step 2: Enumerate triples

Check (1,2,3):

• (1,2) exists
• (1,3) exists
• (2,3) exists

This is a trio.

Step 3: Compute trio degree

$3 + 3 + 3 - 6 = 3$

Minimum degree becomes 3.

No other trios exist.

Final answer:

3

Example 2

n = 7
edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]

Degree array

Node	Degree
1	2
2	2
3	2
4	2
5	3
6	3
7	2

Trio 1: (1,3,4)

All edges exist.

Degree:

$2 + 2 + 2 - 6 = 0$

Minimum becomes 0.

Trio 2: (2,5,6)

Degree:

$2 + 3 + 3 - 6 = 2$

Minimum remains 0.

Trio 3: (5,6,7)

Degree:

$3 + 3 + 2 - 6 = 2$

Minimum remains 0.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^3)	Enumerates all triples of nodes
Space	O(n^2)	Adjacency matrix storage

The dominant operation is the triple nested loop over all node combinations. Each adjacency lookup is constant time because of the matrix representation.

The adjacency matrix requires O(n^2) memory, which is acceptable for n <= 400.

Test Cases

from typing import List

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        connected = [[False] * (n + 1) for _ in range(n + 1)]
        degree = [0] * (n + 1)

        for u, v in edges:
            connected[u][v] = True
            connected[v][u] = True

            degree[u] += 1
            degree[v] += 1

        minimum_degree = float("inf")

        for a in range(1, n + 1):
            for b in range(a + 1, n + 1):
                if not connected[a][b]:
                    continue

                for c in range(b + 1, n + 1):
                    if connected[a][c] and connected[b][c]:
                        trio_degree = degree[a] + degree[b] + degree[c] - 6
                        minimum_degree = min(minimum_degree, trio_degree)

        return -1 if minimum_degree == float("inf") else minimum_degree

solution = Solution()

assert solution.minTrioDegree(
    6,
    [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
) == 3  # Provided example 1

assert solution.minTrioDegree(
    7,
    [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
) == 0  # Provided example 2

assert solution.minTrioDegree(
    4,
    [[1,2],[2,3],[3,4]]
) == -1  # No trio exists

assert solution.minTrioDegree(
    3,
    [[1,2],[2,3],[1,3]]
) == 0  # Single isolated trio

assert solution.minTrioDegree(
    5,
    [[1,2],[2,3],[1,3],[1,4],[2,5]]
) == 2  # Trio with external edges

assert solution.minTrioDegree(
    5,
    [[1,2],[1,3],[2,3],[3,4],[4,5],[3,5]]
) == 1  # Multiple trios

assert solution.minTrioDegree(
    6,
    [
        [1,2],[1,3],[2,3],
        [3,4],[4,5],[3,5],
        [5,6]
    ]
) == 1  # Multiple overlapping trios

Test	Why
Example 1	Validates standard trio detection
Example 2	Validates multiple trios and minimum selection
No trio graph	Ensures algorithm returns -1
Single triangle	Validates isolated trio degree 0
Trio with external edges	Tests proper degree computation
Multiple trios	Ensures minimum is chosen correctly
Overlapping trios	Verifies shared nodes are handled properly

Edge Cases

Graph With No Connected Trio

A graph may contain many edges without containing any triangle. For example, a simple chain or tree structure contains no connected trio.

A buggy implementation might incorrectly assume at least one trio exists and return an invalid value. This solution avoids that issue by initializing the answer to infinity and returning -1 if no trio is ever found.

Trio With Degree Zero

A trio can have no external connections at all. This happens when the graph consists only of the three trio nodes or when the trio is isolated from the rest of the graph.

This case is important because some incorrect implementations accidentally count internal edges as external edges. The subtraction of 6 correctly removes the internal contributions and produces degree 0.

Dense Graphs

The graph may be nearly complete, meaning almost every node pair is connected.

In dense graphs, adjacency lookups happen extremely frequently. Using adjacency lists with linear searches would make the algorithm too slow. The adjacency matrix guarantees constant time edge existence checks and keeps the total runtime within acceptable bounds.

Overlapping Trios

Different trios may share nodes and edges.

For example:

(1,2,3)
(2,3,4)

A buggy implementation might double count or incorrectly skip overlapping structures. Since this solution independently checks every unique node triple, overlapping trios are handled naturally and correctly.