We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Degree of a Connected Trio in a Graph

Number: 1887

Difficulty: Hard

Paid? No

Companies: GoDaddy, Amazon

Problem Description

Given an undirected graph with n nodes and a list of edges, we need to find the minimum degree of any connected trio. A connected trio is a set of three nodes where every pair of nodes is directly connected by an edge. The degree of a connected trio is defined as the total number of edges that have one endpoint in the trio and the other outside the trio. If no trio exists, return -1.

Key Insights

  • Represent the graph using an adjacency list and an edge lookup structure.
  • For each connected pair (u, v), compute the intersection of their neighbor sets to quickly find a third node w that forms a trio with u and v.
  • To avoid duplicate detections of the same trio, enforce an ordering on the nodes (for example, u < v < w).
  • Calculate the trio degree by summing the degrees of the three nodes then subtracting 6 (to remove the internal trio connections, as each internal edge is counted twice in the sum).

Space and Time Complexity

Time Complexity: O(E * d) where E is the number of edges and d is the average degree, because for each edge we compute the intersection of neighbor sets. In the worst-case, it could approach O(n^3) if the graph is very dense. Space Complexity: O(n + E) for storing the adjacency list and other auxiliary data structures.

Solution

We begin by building an adjacency list for each node as well as a set to allow constant-time lookup of whether an edge exists. We also precompute the degree of each node. Then, for every pair of connected nodes (u, v) with u < v, we find all common neighbors w (with w > v) such that (u, v, w) forms a trio. For each trio, its degree is computed as (degree[u] + degree[v] + degree[w] - 6). We keep track of the minimum degree found over all trios. If no trio is identified, we return -1.

Code Solutions

# Python solution with detailed comments
from collections import defaultdict

def minTrioDegree(n, edges):
    # Build an adjacency set for each node
    neighbors = defaultdict(set)
    # Degree dictionary to store the number of neighbors for each node
    degree = [0] * (n + 1)
    
    # Populate the adjacency list and degrees
    for u, v in edges:
        neighbors[u].add(v)
        neighbors[v].add(u)
        degree[u] += 1
        degree[v] += 1

    min_degree = float('inf')
    
    # Iterate through each possible edge (u, v) where u < v
    for u in range(1, n + 1):
        for v in neighbors[u]:
            if u < v:
                # Compute the intersection of neighbors of u and v
                common = neighbors[u] & neighbors[v]
                for w in common:
                    # Enforce ordering to avoid duplicates: u < v < w
                    if v < w:
                        # Compute trio degree: remove trio-internal edges (each internal edge counted twice when summing degree)
                        trio_degree = degree[u] + degree[v] + degree[w] - 6
                        min_degree = min(min_degree, trio_degree)
    
    return min_degree if min_degree != float('inf') else -1

# Example usage:
# n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
print(minTrioDegree(6, [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]))
← Back to All Questions