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


  • 0
    J

    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;
                    }
    
    };
    

  • 0
    J

    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)."


  • 0

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


Log in to reply
 

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