Some problem with python test cases?


  • 0
    A

    Code below gives TLE for different test cases on different submissions. When I copy and paste the same test case in custom input it runs in below 100ms for every test case every time. Also, while copying I noticed that these cases don't have proper formatting. Maybe that is the actual problem? Can someone please confirm

        if not amount:
            return 0
            
        import sys
        dp = [sys.maxint]*(amount+1)
        
        dp[0] = 0
        
        coins = sorted(coins)
        
        for i in xrange(1,amount+1):
            for coin in coins:
                if coin > i:
                    break
                else:
                    if dp[i-coin] != sys.maxint:
                        dp[i] = min(dp[i], dp[i-coin] + 1)
                        
        return dp[-1] if dp[-1] != sys.maxint else -1

  • 0

    No, the formatting isn't the problem, your solution is just too slow.


  • 0
    A

    Could you please suggest some improvements. Below is my accepted code but I don't understand why this little improvement should matter.
    `if not amount:
    return 0

        dp = [amount+1]*(amount+1)
        
        dp[0] = 0
        
        coins = sorted(coins)
        
        for i in xrange(1,amount+1):
            for coin in coins:
                if coin > i:
                    break
                else:
                    #if dp[i-coin] != sys.maxint:
                    dp[i] = min(dp[i], dp[i-coin] + 1)
                        
        return dp[-1] if dp[-1] != amount+1 else -1`
    

    Also, if you post your own python version it would be highly appreciated. I find something new in them always.


  • 0
    A

    I have tried this too without significant improvement(still beyond 1000ms):

    for coin in coins:
         for i in xrange(coin,amount+1):
               dp[i] = min(dp[i], dp[i-coin]+1)
        
        return dp[-1] if dp[-1] != amount + 1 else -1`

  • 0

    Ok, here are mine. I got under 1000ms, but not by much.


  • 0

    I had experimented with your code as well, and removing the extra test if dp[i-coin] != sys.maxint seemed to help the most. I guess it doesn't help very often/much, and it hurts too much to always run that extra test.

    It's a bit like that if not amount: return 0 thing that you and many others do. It's not needed, the rest of your solution would perfectly handle that case as well. And speedwise it only helps a tiny bit and only in rare cases that are fast anyway, and it slows down every other case a bit (so overall I'd say it hurts more than it helps, if it makes any difference at all). I only ever do something like that when I really need it, i.e., when the rest doesn't work otherwise. (Though not because of speed but because I don't like unnecessary code.)


  • 0
    A

    Thanks a lot for the suggestion. But I am still not satisfied with the speed. C++ gives much better result. I understand that python is slower but this slow?


Log in to reply
 

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