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.
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,4,3] with degree 0.
- [2,5,6] with degree 2.
- [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.
Also See: Nth Ugly numbers puesudo code using min heap

SOLUTION
Program: Shopping Patterns Solution in 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: Shopping Patterns Solution in 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: Shopping Patterns Solution in Java
Explanation:
- The 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;
}
}
Amazon OA 2023 Questions with Solution
- Reorder Data in Log Files Solution Amazon OA 2023
- Top K Frequent Words Solution Amazon OA 2023
- Trees Height Solution Amazon OA SDE 2023
- Counting Binary Substrings Amazon OA 2023
- Grid Connections Amazon OA 2023
- Shipment Imbalance Amazon OA 2023
- Max Profit Amazon OA 2023
- Find Lowest Price Amazon OA 2023
- Decode String Frequency Amazon OA 2023
- Simple Cipher Amazon OA 2023
- Valid Discount Coupons Amazon OA 2023 Solution
- Count Maximum Teams Amazon OA 2023
- Minimum Coin Flips Amazon OA 2023
- Max Average Stock Price Amazon OA 2023 Solution
- Robot Bounded In Circle Amazon OA 2023
- Shopping Options Amazon OA 2023 Solution
- Fill The Truck Maximum Units on a Truck Amazon OA Solution
- Maximize Score After N Operations Number Game Solution Amazon OA 2023
- Slowest Key Amazon OA 2023 Solution
- Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
- Split String Into Unique Primes Amazon OA 2023 Solution
- Storage Optimization Amazon OA 2023 Solution
- Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
- Autoscale Policy Utilization Check Amazon OA 2023
- Optimal Utilization Solution Amazon OA 2023
- Merge Two Sorted Lists Solution Amazon OA 2023
- Two Sum Unique Pairs Solution Amazon OA 2023
- Amazon Music Pairs Amazon OA 2023 Solution
- Class Grouping Amazon OA 2023 Solution
- Find Max products Amazon OA 2023 Solution
- Get encrypted number Amazon OA 2023 Solution
- Find Total Imbalance Amazon OA 2023 Solution
- Find Total Power Amazon OA 2023 Solution