O(n^2) Time limit exceed


  • 0
    P

    The last question:
    N<=1000;
    Why O(n^2) get TLE


  • 0

    Could you please paste your code in your post? Without your code others won't be able to troubleshoot the problem for you, thanks.


  • 0
    N
    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            vector <unordered_map <long long , int>> ans;
            
            // cout<<A.size()<<endl;
            long long num = 0;
            int n = A.size();
            
            if(n == 0) return 0;
            
            unordered_map <long long , int> tmp_ans;
            
            for(int i = 0 ; i < n ; i++){
                if(tmp_ans.find(A[i]) == tmp_ans.end()){
                    tmp_ans[A[i]] = 1;
                }else
                    tmp_ans[A[i]] ++;
            }
            
            // calculate duplicate numbers 
            for(auto i : tmp_ans){
                long long x = i.second;
                if(x >= 3){
                    
                    if(x % 2 == 0)
                        num += (long long)pow(2.0 , (double) x) - 1 -   x / 2 * (x - 1) - x;
                    else
                        num += (long long)pow(2.0 , (double) x) - 1 -   (x - 1) / 2 * x - x;
                    
                }
            }
            
            
            for(int i = 0 ; i < n ; i++){
                // keep a hashmap with the key to be the distance between two numbers and value to be the number of elements
                unordered_map <long long , int> tmp;
                for(int j  = 0 ; j < i ; j++){
                    long long dis = (long long)A[i] - (long long)A[j];
                    
                    if(dis == 0)
                        continue;
                    
                    if(ans[j].find(dis) == ans[j].end()){
                        if(tmp.find(dis) == tmp.end())
                            tmp[dis] = 2;
                        else
                            tmp[dis]++;
                    }else{
                        num += (ans[j][dis] - 1);
                        if(tmp.find(dis) == tmp.end())
                            tmp[dis] = ans[j][dis] + 1;
                        else
                            tmp[dis] += ans[j][dis];
                    }
                }
                
                ans.push_back(tmp);    
                
            }
            
            
            return num;
        }
    };
    

    Hi , I think my solution is O(n^2) , I used only two loops.
    And it got a TLE when n = 1000.
    Could you help me figure out why it is TLE?


  • 2
    P

    This python solution got accepted:

    class Solution(object):
        def numberOfArithmeticSlices(self, A): 
            ans = 0;
            dp = [{} for i in xrange(len(A))]
            for i in xrange(1, len(A)):
                for j in xrange(0, i): 
                    dist = A[i] - A[j]
                    s = dp[j].get(dist, 0) + 1
                    dp[i][dist] = dp[i].get(dist, 0) + s
                    ans += s
                ans -= i
            return ans;
    

    but almost identical solution in c++ got MLE/TLE:

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int ans = 0;
            vector<unordered_map<long long, int>> dp(A.size());
            for (int i = 1; i < A.size(); i++) {
                for (int j = 0; j < i; j++) {
                    long long dist = (long long)A[i] - A[j];
                    auto it = dp[j].find(dist);
                    int s = (it == dp[j].end() ? 0 : it->second) + 1;
                    dp[i][dist] += s;
                    ans += s;
                }
                ans -= i;
            }
            return ans;
        }
    };
    

  • 0
    P
    typedef long long LL;
    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int n = A.size();
            if(n<3) return 0;
            vector<unordered_map<LL,LL> > dp(n);
            vector<unordered_map<LL,LL> > par(n);
            unordered_map<LL,LL> ct;
            LL count = 0;
            for(int i=0;i<n;i++){
                ct[A[i]]++;
                for(int j=0;j<i;j++){
                    LL diff = (LL)A[i]-(LL)A[j];
                    if(diff == 0){
                        continue;
                    }
                    par[i][diff] += 1;
                    dp[i][diff] += dp[j][diff] + par[j][diff];
                    count += dp[j][diff]+par[j][diff];
                }
            }
            for(auto pr:ct) if(pr.second>2){
                LL k = pr.second;
                count += (1LL<<k) - 1 - k - k*(k-1)/2;
            }
            return count;
        }
    };
    

    Sry, forgot to post my code.
    I only used 2 loops, and it is definitely O(n^2), but got TLE


  • 0

    My JavaScript solution gets MLE. And it is basically the same as nehcdnr's solution.

    var numberOfArithmeticSlices = function (A) {
        let res = 0;
        const dp = Array(A.length).fill(0).map(() => new Map());
    
        for (let i = 0; i < A.length; i++) {
            for (let j = 0; j < i; j++) {
                const diff = A[i] - A[j];
    
                let count = 1;
                if (dp[j].has(diff)) {
                    count += dp[j].get(diff);
                    res += dp[j].get(diff);
                }
    
                dp[i].set(diff, (dp[i].get(diff) || 0) + count);
            }
        }
    
        return res;
    };
    

  • 0
    J
    This post is deleted!

  • 0
    C

    @pumpkingg Can you explain the logic?


  • 0
    J

    @pumpkingg I have a question regarding your python code. Why we need ans -= i? Could you please explain this line of code?


Log in to reply
 

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