This code has O(n^3) time complexity but gives a TLE?


#1

vector Solution::equal(vector &A) {

if(A.size()<4 || A.size()>INT_MAX)
return (vector<int>)NULL;

unordered_multimap<long long int, pair<int,  int> > m;

vector<int> v_min;
pair< int, int> q,r;
for( int i = 0; i<A.size()-1; i++)
{
for( int j = i+1; j<A.size(); j++)
{
    long long int sum = (A[i] + A[j]);
    
    m.emplace(sum, make_pair(i,j));
}
}

for(int i=0; i<m.bucket_count(); i++)
{
    for(auto j=m.begin(i); j!=m.end(i); j++)
    {
        q = j->second;
        
        for(auto k=m.begin(i); k!=m.end(i); k++)
        {
            r = k->second;
            if(q.first<r.first && q.second!=r.first && q.second!=r.second)
            {
                vector<int> v;
                v.push_back(q.first);
                v.push_back(q.second);
                v.push_back(r.first);
                v.push_back(r.second);
                if(v_min.empty())
                v_min = v;
                if(v<v_min)
                v_min = v;
            }
        }
    }
}

return v_min.empty()?(vector<int>)NULL:v_min;

}


#2

Because a solution with O(n^2) is possible.