Can anyone tell me why this is a TLE? It's driving me nuts


  • 0
    B

    And also I do not understand why everyone is using a data structure to store info. Is it bad to do it in my way? Any help is really appreciated.

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            int deg[n] = {0};
            int sz = edges.size();
            vector<int> ans;
            if (sz == 0) {ans.push_back(0); return ans;}
            unordered_set<int> my_set;
            for (int i = 0; i < n; i++) my_set.insert(i);
            //counting degrees at the beginning
            for (int i = 0; i < sz; i++) {
                pair<int, int> thisPair = edges[i];
                deg[thisPair.first]++;
                deg[thisPair.second]++;
            }
            //deleting 
            int count = n;
            while (count > 2) {
                int i = 0;
                for (; i < n; i++) {
                    if (deg[i] == 1) {
                        deg[i] = 0;
                        for (int j = 0; j < sz; j++) {
                            if (edges[j].first == i) {deg[edges[j].second]--; break;}
                            if (edges[j].second == i) {deg[edges[j].first]--; break;}
                        }
                        count--;
                        my_set.erase(i);
                    }
                }
            }
            for (unordered_set<int>::iterator it = my_set.begin(); it != my_set.end(); it++) {
                ans.push_back(*it);
            }
            return ans;
        }
    };

  • 0
    S

    if dig[i] != 1 for any i, then count is not decremented, and thereby the outer while loop is not terminating.


  • 0
    B

    Oh thanks so much!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.