# Time limit exceeded with O(n^3 log n)

• I'm getting TLE on the last case. If I run the 16ms solution vs my solution on my local machine it doesn't perform much better than a few ms. Why would that be enough to cause TLE, especially for an O(n^3 log n) algorithm which is the best I think we are going to get out it.

``````class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<int>::iterator i,j,k,l,z;
vector<vector<int>> returnVector;
int tempTarget;
string s;

if(nums.size() < 4)
return returnVector;

unordered_set<string> found;

sort(nums.begin(), nums.end());
z = nums.end();

if(*(z-1)+*(z-2)+*(z-3)+*(z-4) < target)
return returnVector;

for(i = nums.begin(); i + 3 != z; i++)
{
if(*i+*(i+1)+*(i+2)+*(i+3)>target) break;
for(j = i + 1; j + 2 != z; j++)
{
if(target-*i-*j-*(z-1) > *(z-1)) continue;
l = z;
for(k = j + 1; k + 1 != l && k != l; k++)
{
tempTarget = target - *i - *j - *k;

if(tempTarget < *(k+1)) continue;
if(tempTarget > *(l-1)) continue;

l = lower_bound(k+1,l,tempTarget);
if(l != z && *l == tempTarget)
{
s = buildString(*i,*j,*k,tempTarget);
if(found.find(s) == found.end())
{
found.insert(s);
returnVector.push_back({*i,*j,*k,tempTarget});
}
}
}
}
}

return returnVector;
}
private:
string buildString(int i, int j, int k, int l)
{
vector<int> temp({i,j,k,l});
sort(temp.begin(), temp.end());

string s(to_string(i) + " " + to_string(j) + " " + to_string(k) + " " + to_string(l) + " ");

return s;
}

};
``````

• OK I added the one missing case into the second for loop

``````if(*i+*j+*(j+1)+*(j+2) > target) break;
``````

and on my local machine it performs exactly the same as the 16ms solution but on here it's like 100+ms off.

These algorithms should really be testing worst case scenario and accept all solutions that fit the minimum big O, which for this solution would be O(n^3 log n)

Worst case you must enumerate through all triples of items in an n-element universe + do a binary search for each enumeration. Which comes out to O(n^3 log n)

This is straight out of "The Algorithm Design Manual" Second Edition

"Cubic functions, f(n) = n3 – Such functions enumerate through all triples of
items in an n-element universe."

"Logarithmic functions, f(n) = log n – Logarithmic time-complexity shows up
in algorithms such as binary search. Such functions grow quite slowly as n
gets big, but faster than the constant function (which is standing still, after
all)."

• Just do it in O(n^3) like everybody(?) else.

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