# Shopping Patterns Solution Amazon OA 2023

## 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. [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: Shopping Patterns Solution in C++

``````class Solution {
public:

bool visited;
int minTrioDegree(int n, vector<vector<int>>& edges) {

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];
int end = edges[i];
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:

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)

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, degrees.getOrDefault(edge, 0) + 1);
degrees.put(edge, degrees.getOrDefault(edge, 0) + 1);
isEdge[edge][edge] = true;
isEdge[edge][edge] = true;
}

for (int[] edge : edges) {
for (int i = 1; i <= n; i++) {
if (isEdge[i][edge] && isEdge[i][edge]) {
// subtract 6 because we do not count inner edges of a trio
int degree = degrees.get(i) + degrees.get(edge) + degrees.get(edge) - 6;
min = Math.min(min, degree);
}
}
}

if (min == Integer.MAX_VALUE)
return -1;
return min;
}
}``````