Shopping Patterns - Company-specific OAs / Amazon OA

Problems
1

https://algo.monster/problems/shopping_patterns

2

That last “optimization” is super interesting. It doesn’t change time complexity, but it makes a big difference in the leetcode performance lol.

3

Leetcode solution:

class Solution {
    List<HashSet<Integer>> adjacency = new ArrayList<>();
    
    public int minTrioDegree(int n, int[][] edges) {
        int[] degree = new int[n];
        buildAdjacency(n, edges, degree);
        return getMinTrioDegree(adjacency.size(), degree);
    }
    
    private void buildAdjacency(int n, int[][] edges, int[] degree) {
        for (int i = 0; i < n; i++) {
            adjacency.add(new HashSet<>());
        }
        
        for (int i = 0; i < edges.length; i++) {
            //converting the vertices into 0 based index
            int u = edges[i][0] - 1;
            int v = edges[i][1] - 1;
            
            degree[u]++;
            degree[v]++;
            
            adjacency.get(u).add(v);
            adjacency.get(v).add(u);
        }
    }
    
    private Integer getMinTrioDegree(int n, int[] degree) {
        int minimumDegree = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                if (!adjacency.get(j).contains(i)) continue;
                for (int k = j + 1; k < n; k++) {
                    if (adjacency.get(k).contains(i) && adjacency.get(k).contains(j)) {
                        int totalDegree = degree[i] + degree[j] + degree[k] - 6;
                        minimumDegree = Math.min(minimumDegree, totalDegree);
                    }
                }
            }
        }
        
        return minimumDegree == Integer.MAX_VALUE ? -1 : minimumDegree;
    }
}