Doubt About Time Complexity
I solved this question using dfs + map/set. Time taken was nlogn. usually for n=1e5, nlogn solution works fine but here, I was able to solve only 25 test cases(
I solved this question using dfs + map/set. Time taken was nlogn. usually for n=1e5, nlogn solution works fine but here, I was able to solve only 25 test cases(map)/23 tc(set). Is there a way to see if an nlogn solution will be accepted or not in a contest (**other than ofcourse submitting and getting a TLE, please dont suggest this in comments :D**)\n\nCode (C++) for reference\n\n\n//MAP\nclass Solution {\n\npublic:\n\n    vector<int> parents,nums;\n    vector<int> dp;\n    void solve(map<int,int>& check, int node, vector<vector<int>>& v){\n\t\n        if(v[node].empty()){\n            check.erase(nums[node]);\n            dp[node]=(nums[node]==1?2:1);\n            return;\n        }\n        for(auto val:v[node]){\n            if(dp[val]!=-1) continue; //I know this is a redundant step\n            solve(check,val,v);\n        }\n        check.erase(nums[node]);\n        dp[node]=check.begin()->first;\n        return;\n    }\n    \n    \n    vector<int> smallestMissingValueSubtree(vector<int>& pt, vector<int>& nm) {\n        parents=pt; nums=nm;\n        int n=parents.size();\n        int node=0;\n        vector<vector<int>> v(n+1);\n        dp=vector<int>(n,-1);\n        map<int,int> check;\n        for(int i=1;i<=1e5+10;i++){\n            check[i]=1;\n        }\n        for(int i=1;i<n;i++){\n            v[parents[i]].push_back(i);\n        }\n        int maxval=INT_MIN;\n        for(auto val:v[node]){\n            map<int,int> temp=check;\n            solve(temp,val,v);\n        }\n        sort(nums.begin(),nums.end());\n        for(int i=0;i<=nums.size();i++){\n            if(i==nums.size()){\n                dp[0]=nums.size()+1; break;\n            }\n            if(i+1!=nums[i]){\n                dp[0]=i+1; break;\n            }\n        }\n        return dp;\n        \n    }\n};\n\n\n\n//SET\nclass Solution {\npublic:\n\n    vector<int> parents,nums;\n    vector<int> dp;\n    void solve(set<int>& check, int node, vector<vector<int>>& v){\n        if(v[node].empty()){\n            check.erase(nums[node]);\n            dp[node]=(nums[node]==1?2:1);\n            return;\n        }\n        for(auto val:v[node]){\n            if(dp[val]!=-1) continue;\n            solve(check,val,v);\n        }\n        check.erase(nums[node]);\n        dp[node]=*check.begin();\n        return;\n    }\n    \n    \n    vector<int> smallestMissingValueSubtree(vector<int>& pt, vector<int>& nm) {\n        parents=pt; nums=nm;\n        int n=parents.size();\n        int node=0;\n        vector<vector<int>> v(n+1);\n        dp=vector<int>(n,-1);\n        set<int> check;\n        for(int i=1;i<=1e5+10;i++){\n            check.insert(i);\n        }\n        for(int i=1;i<n;i++){\n            v[parents[i]].push_back(i);\n        }\n        int maxval=INT_MIN;\n        for(auto val:v[node]){\n            set<int> temp=check;\n            solve(temp,val,v);\n        }\n        sort(nums.begin(),nums.end());\n        for(int i=0;i<=nums.size();i++){\n            if(i==nums.size()){\n                dp[0]=nums.size()+1; break;\n            }\n            if(i+1!=nums[i]){\n                dp[0]=i+1; break;\n            }\n        }\n        return dp;\n        \n    }\n};\n\n\nWill appreciate any kind of help/suggestions.
['Depth-First Search', 'C', 'Ordered Set']