Page Contents
Shopping Patterns 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
.
Also See: Amazon OA Online Assessment 2021 Questions and Answers
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.
Solution
Program C++
class Solution { public: bool visited[401][401]; int minTrioDegree(int n, vector<vector<int>>& edges) { vector<unordered_set<int>>adj(n+1); memset(visited,false,sizeof(visited)); int degree[n+1]; for(int i=0;i<n+1;i++) degree[i]=0; for(int i=0;i<edges.size();i++){ int start = edges[i][0]; int end = edges[i][1]; visited[start][end]=true; visited[end][start]=true; degree[start]++; degree[end]++; } int result = INT_MAX; for(int i=1;i<=n-2;i++){ for(int j=i+1;j<=n-1;j++){ for(int k=j+1;k<=n;k++){ if(connected(i,j,k)){ int count = 0; count+=degree[i]-2; count+=degree[j]-2; count+=degree[k]-2; result=min(result,count); } } } } return result==INT_MAX ? -1: result; } bool connected(int i,int j,int k){ if(!visited[i][j] || !visited[i][k]) return false; if(!visited[j][i] || !visited[j][k]) return false; if(!visited[k][i] || !visited[k][j]) return false; return true; } };
Program Python
class Solution: def minTrioDegree(self, n: int, edges: List[List[int]]) -> int: g = defaultdict(set) for a, b in edges: g[a].add(b) g[b].add(a) d = {n:len(g[n]) for n in g} res = inf for n in g: for m in g[n]: for o in g[n] & g[m]: res = min(res, d[n]+d[m]+d[o]-6) g[o].discard(n) g[m].discard(n) return res if res < inf else -1
Program Java
he HashMap degrees keeps track of the degree for each vertex.
boolean[][] isEdge keeps track of whether (i, j) is an edge.
Then we just iterate through all edges (i, j), and for each edge, iterate through all nodes k, if (i, k) and (j, k) are also edges, then this is a trio. We just use the degrees we stored in the hashmap to calculate the total degrees.
The complexity is O(E * V), where E is the number of edges, and V is the number of vertices (which is N). In worst case scenario, there would be ~N^2 edges, so the time complexity is O(N^3).
class Solution { public int minTrioDegree(int n, int[][] edges) { int min = Integer.MAX_VALUE; Map<Integer, Integer> degrees = new HashMap<>(); // vertex, degree boolean[][] isEdge = new boolean[n + 1][n + 1]; for (int[] edge : edges) { degrees.put(edge[0], degrees.getOrDefault(edge[0], 0) + 1); degrees.put(edge[1], degrees.getOrDefault(edge[1], 0) + 1); isEdge[edge[0]][edge[1]] = true; isEdge[edge[1]][edge[0]] = true; } for (int[] edge : edges) { for (int i = 1; i <= n; i++) { if (isEdge[i][edge[0]] && isEdge[i][edge[1]]) { // subtract 6 because we do not count inner edges of a trio int degree = degrees.get(i) + degrees.get(edge[0]) + degrees.get(edge[1]) - 6; min = Math.min(min, degree); } } } if (min == Integer.MAX_VALUE) return -1; return min; } }
Also See: AMCAT Study Materials, Preparation Guide
Also See: Microsoft Online Assessment Questions and Solution
Amazon Online Assessment Questions:
- Robot Bounded in Box
- Number Game
- Find All Combination of Numbers Sum to Target / Shopping Options
- Fill the Truck
- Music Pairs
- Slowest key
- Five Star Seller
- Split String Into Unique Primes
- Storage Optimization
- Minimum Difficulty of a Job Schedule
- Autoscale Policy, Utilization Check
- Optimal Utilization
- Merge Two Sorted Lists
- Two Sum Unique Pairs
- Shopping Patterns
- Reorder Data in Log Files
- Top K Frequent Words
- Trees Height
- Counting Binary Substrings Amazon OA Solution
- Grid Connections Amazon OA Solution
- Shipment Imbalance Amazon OA Solution
- Max Profit Amazon OA Solution
- Find Lowest Price Amazon OA Solution
- Simple Cipher Amazon OA Solution
- Decode String Frequency Amazon OA Solution
- Valid Discount Coupons Amazon OA Solution
- Count Maximum Teams Amazon OA Solution
- Minimum Coin Flips Amazon OA Solution