1761. Minimum Degree of a Connected Trio in a Graph LeetCode Solution
In this guide, you will get 1761. Minimum Degree of a Connected Trio in a Graph LeetCode Solution with the best time and space complexity. The solution to Minimum Degree of a Connected Trio in a Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Degree of a Connected Trio in a Graph
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.
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.
Complexity Analysis
Time Complexity: O(n^3)
Space Complexity: O(n^2)
1761. Minimum Degree of a Connected Trio in a Graph LeetCode Solution in C++
class Solution {
public:
int minTrioDegree(int n, vector<vector<int>>& edges) {
int ans = INT_MAX;
vector<unordered_set<int>> graph(n);
vector<int> degrees(n);
for (const vector<int>& edge : edges) {
const int u = edge[0] - 1;
const int v = edge[1] - 1;
// Store the mapping from `min(u, v)` to `max(u, v)` to speed up.
graph[min(u, v)].insert(max(u, v));
++degrees[u];
++degrees[v];
}
for (int u = 0; u < n; ++u)
for (const int v : graph[u])
for (const int w : graph[u])
if (graph[v].contains(w))
ans = min(ans, degrees[u] + degrees[v] + degrees[w] - 6);
return ans == INT_MAX ? -1 : ans;
}
}; /* code provided by PROGIEZ */
1761. Minimum Degree of a Connected Trio in a Graph LeetCode Solution in Java
class Solution {
public int minTrioDegree(int n, int[][] edges) {
int ans = Integer.MAX_VALUE;
Set<Integer>[] graph = new Set[n];
int[] degrees = new int[n];
for (int i = 0; i < n; ++i)
graph[i] = new HashSet<>();
for (int[] edge : edges) {
final int u = edge[0] - 1;
final int v = edge[1] - 1;
// Store the mapping from `min(u, v)` to `max(u, v)` to speed up.
graph[Math.min(u, v)].add(Math.max(u, v));
++degrees[u];
++degrees[v];
}
for (int u = 0; u < n; u++)
for (final int v : graph[u])
for (final int w : graph[u])
if (graph[v].contains(w))
ans = Math.min(ans, degrees[u] + degrees[v] + degrees[w] - 6);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
} // code provided by PROGIEZ
1761. Minimum Degree of a Connected Trio in a Graph LeetCode Solution in Python
class Solution:
def minTrioDegree(self, n: int, edges: list[list[int]]) -> int:
ans = math.inf
graph = [set() for _ in range(n)]
degrees = [0] * n
for u, v in edges:
u -= 1
v -= 1
# Store the mapping from `min(u, v)` to `max(u, v)` to speed up.
graph[min(u, v)].add(max(u, v))
degrees[u] += 1
degrees[v] += 1
for u in range(n):
for v in graph[u]:
for w in graph[u]:
if w in graph[v]:
ans = min(ans, degrees[u] + degrees[v] + degrees[w] - 6)
return -1 if ans == math.inf else ans # code by PROGIEZ
