LeetCode 1761: Minimum Degree of a Connected Trio in a Graph Solution

Master LeetCode problem 1761 (Minimum Degree of a Connected Trio in a Graph), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1761. Minimum Degree of a Connected Trio in a Graph

Hard

Graph

Problem Explanation

Explanation:

To solve this problem, we can iterate through all possible connected trios and calculate their degrees. We can then keep track of the minimum degree found so far.

Create a graph representation using an adjacency list.
Iterate through all possible trios of nodes.
For each trio, calculate the degree by counting the number of edges outside the trio.
Update the minimum degree found so far.
Return the minimum degree as the result.

Time Complexity: O(n^3), where n is the number of nodes.

Space Complexity: O(n^2) for the adjacency list.

Solution Code

class Solution {
    public int minTrioDegree(int n, int[][] edges) {
        int[] degree = new int[n + 1];
        boolean[][] connected = new boolean[n + 1][n + 1];
        
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            degree[u]++;
            degree[v]++;
            connected[u][v] = true;
            connected[v][u] = true;
        }
        
        int minDegree = Integer.MAX_VALUE;
        
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (connected[i][j]) {
                    for (int k = j + 1; k <= n; k++) {
                        if (connected[i][k] && connected[j][k]) {
                            int trioDegree = degree[i] + degree[j] + degree[k] - 6;
                            minDegree = Math.min(minDegree, trioDegree);
                        }
                    }
                }
            }
        }
        
        return minDegree == Integer.MAX_VALUE ? -1 : minDegree;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1761 (Minimum Degree of a Connected Trio in a Graph)?

This page provides optimized solutions for LeetCode problem 1761 (Minimum Degree of a Connected Trio in a Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1761 (Minimum Degree of a Connected Trio in a Graph)?

The time complexity for LeetCode 1761 (Minimum Degree of a Connected Trio in a Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1761 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1761 in Java, C++, or Python.

Back to LeetCode Solutions