Accepted when used array of int and TLE when used unordered_map for memoisation in recursion


  • 0
    D

    This code shoe TLE, but when I replace "unordered_map<int,int> mymap " with array of int for memoisation , it got accepted ........... can some one tell why ?

    class Solution {

    public:

    unordered_map<int,int> mymap;
    int find(int n)
    {
    unordered_map<int,int>::iterator it;

        it=mymap.find(n);
    
        if(it!=mymap.end())
        return it->second;
        
        int x,ans=n,i;
        if(n==1)
        return 1;
        
        if(n<0)
        return -1;
        
        if(n==0)
        return 0;
    
        for(i=1;i<=sqrt(n);i++)
        {
            if(i*i<=n)
            {
                    x=find(n-i*i);
                    if(x>0)
                    ans=min(ans,x+1);
                
            }
        }
        mymap.insert(make_pair(n,ans));
        return ans;
    }
    int numSquares(int n) {
        int ans=find(n);
        
        return ans;
    }
    

    };


Log in to reply
 

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