Why does this time out? Is the time complexity not O(n^2logn)?
deleted_user
19

Question 15: 3sum:

I am getting time limit exceeded on the leetcode platform, but I have noticed several other O(n^2logn) solutions being accepted. Am I correct in believing that the time complexity of my solutions is O(n^2logn)? Is my binary search implemented correctly? The only guess I have to as to what is causing my solution to time out, when other similarly implemented O(n^2logn) solutions are accepted, is some sort of error in my binary search loop.

Please help me get to the bottom of this. I have posted the code below.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        sort(nums.begin(),nums.end());
        
        vector<vector<int>> ans;
        
        vector<vector<int>> ans2;
        
        unordered_set<string> myset;
        
        unordered_set<string>::iterator itr; 
       
        int L,M,R,target,temp;
        
        string s="";
        
        
        for(int i=0;i<nums.size() or nums[i]<0 or i!=0 ;i++) for(int j=i+1;j<nums.size();j++){
            
            L=j+1;
            R=nums.size()-1;
            target=(nums[i]+nums[j])*-1;
            
            while(R>=L){
                M=L+(R-L)/2;
                
                if(nums[M]==target){
        
                   ans.push_back({nums[i],nums[j],nums[M]});
                    
                }
                
                if(nums[M]>=target){
                    R=M-1;
                }else{
                    L=M+1;
                }      
            }
        }
        
        
        for(int i=0;i<ans.size();i++){
            
            s=to_string(ans[i][0])+to_string(ans[i][1])+to_string(ans[i][2]);
            
            itr=myset.find(s);
            
            if(itr==myset.end()){
                ans2.push_back(ans[i]);
                myset.insert(s);
            }
            
        }
        
        return ans2;
    }
};
Comments (0)