TLE on 3-Sum Problem on Leetcode

Revision en1, by tejas2, 2023-08-06 11:21:07

This is my submission for 3Sum Problem on Leetcode and the complexity comes out to be O(n^2), since I have used a nested for loop for the length of the nums array (nums.length()<=3000). However, I am getting TLE on all zeros case. Can anyone help me understand what is wrong with my complexity? The code file with the testcase is attached.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        set<vector<int>> ans;
        vector<int> present(200001,0);
        int n = nums.size();
        for(int x=0;x<n;x++)
        {
            int val = nums[x];
            int ind = val + 100000;
            present[ind]++;
        }

        for(int x=0;x<n;x++)
        {
            int v1 = nums[x];
            present[v1+100000]--;
            for(int y=0;y<n ;y++)
            {
                if(y==x)
                {
                    continue;
                }
                int v2 = nums[y];
                present[v2+100000]--;
                int rem = -v1-v2;
                
                if(rem>=-100000 && rem<=100000 && present[rem+100000]>0)
                {
                    vector<int> pans;
                    pans.push_back(v1);
                    pans.push_back(v2);
                    pans.push_back(rem);
                    sort(pans.begin(),pans.end());
                    if(v1+v2+rem==0)
                    {
                        // cout<<"inserting : {"<<v1<<" "<<v2<<" "<<rem<<"}"<<endl;
                        ans.insert(pans);
                    }
                }
                present[v2+100000]++;
            }
            present[v1+100000]++;
        }
        vector<vector<int>> ret;
        for(auto i : ans)
        {
            ret.push_back(i);
        }
        return ret;
    }
};
Tags dp, 2 pointers, implementations, complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English tejas2 2023-08-06 11:21:07 1952 Initial revision (published)