Why does my O(n^2) algorithm get TLE?


  • 0
    Z
    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            auto two_sum = set<int>();
            int best = nums[0]+nums[1]+nums[2];
            for (int i = 0; i < nums.size(); i++) {
                auto it = two_sum.upper_bound(target-nums[i]);
                if (it != two_sum.end()) {
                    int candidate = nums[i] + *it;
                    if (abs(candidate-target) < abs(best-target)) {
                        best = candidate;
                    }
                }
                if (it != two_sum.begin()) {
                    it--;
                    int candidate = nums[i] + *it;
                    if (abs(candidate-target) < abs(best-target)) {
                        best = candidate;
                    }
                }
    
                
                for (int j = 0; j < i; j++) {
                    two_sum.insert(nums[i]+nums[j]);
                }
            }
            
            return best;
            
        }
    };
    

  • 0
    R

    I can't tell you why for sure, but I can tell you how to fix it.

    Add an optimization to return once you've found an answer that can't be beat. I'm running a O(n^3) algorithm with a for(for(for))) loop, but with the little heuristic I described it passes.

    I'm intentionally being a bit cryptic here so as not to give it away too blatantly. If you want me to come right out and tell you what I'm talking about just let me know.


  • 0
    X

    I didn't read your algorithm carefully. But I guess the slowness comes from set<int>(). Because set is implemented with binary search tree and it will reorganize the order every time a new value is inserted. Could you try to use unordered_set?


Log in to reply
 

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