Krammer's blog

https://leetcode.com/problems/minimum-degree-of-a-connected-trio-in-a-graph/ from Amazon

Thinking process:

Basically just use brute force. We usually translate a graph into an adjacent list, so I first wrote something like this.

 1class Solution {
 2public:
 3    int minTrioDegree(int n, vector<vector<int>>& edges) {
 4        vector<vector<int>> es(n+1);
 5        int ans = INT_MAX;
 6        vector<unordered_set<int>> nei(n+1);
 7        for (auto& e : edges) {
 8            es[e[0]].push_back(e[1]);
 9            nei[e[0]].insert(e[1]);
10            es[e[1]].push_back(e[0]);
11            nei[e[1]].insert(e[0]);
12        }
13        for (int i=1; i<=n; i++) {
14            if (es[i].size() >= 2) {
15                int L = es[i].size();
16                for (int j=0; j<L; j++) {
17                    for (int k=j+1; k<L; k++) {
18                        if (nei[es[i][j]].count(es[i][k])) {
19                            // cout << i << " " << es[i][j] << " " << es[i][k] << endl;
20                            ans = min(ans, (int)(es[i].size() + es[es[i][j]].size() + es[es[i][k]].size() - 6));
21                        }
22                    }
23                }
24            }
25        }
26        return ans != INT_MAX ? ans : -1;
27    }
28};

The time complexity of this is O(V*(E^2)), since E is V^2, the time complexity is actually O(V^5) which is too huge. I got a TLE of course.

This problem is intersting because this is where we should use adjacent matrix. With adjacent matrix, we can lower the time complexity to O(V^3) by just using brute force. No other special tricks.

Here is the code.

 1class Solution {
 2public:
 3    int minTrioDegree(int n, vector<vector<int>>& edges) {
 4        vector<vector<int>> adj(n+1, vector<int>(n+1));
 5        vector<int> deg(n+1);
 6        int ans = INT_MAX;
 7        for (auto e : edges) {
 8            adj[e[0]][e[1]] = 1;
 9            adj[e[1]][e[0]] = 1;
10            deg[e[0]]++;
11            deg[e[1]]++;
12        }
13        for (int i=1; i<=n; i++) {
14            for (int j=i+1; j<=n; j++) {
15                for (int k=j+1; k<=n; k++) {
16                    if (adj[i][j] and adj[j][k] and adj[i][k]) {
17                        ans = min(ans, deg[i] + deg[j] + deg[k] - 6);
18                    }
19                }
20            }
21        }
22        return ans != INT_MAX ? ans : -1;
23    }
24};

Editorial: LeetCode 1761 Minimum Degree of a Connected Trio in a Graph