Unbelievable! Two almost the same python code, one gets Accepted while one gets Time Limit Exceeded.


  • -1
    J

    The Accepted code:

    class Solution(object):
        def coinChange(self, coins, amount):        
            coins.sort()
            INT_MAX = 9999999999
            f = [INT_MAX] * (amount + 1)
            f[0] = 0
            for i in xrange(1, amount + 1):
                # Here comes **the only difference**
                for coin in coins:
                    if  i < coin:
                        break
                    f[i] = min(f[i], f[i-coin] + 1)
            return f[amount] if f[amount] != INT_MAX else -1
    

    The TLE code:

    class Solution(object):
        def coinChange(self, coins, amount):
            coins.sort()
            INT_MAX = 9999999999
            f = [INT_MAX] * (amount + 1)
            f[0] = 0
            for i in xrange(1, amount + 1):
                # Here comes **the only difference**
                for j in range(len(coins)):
                    if  i < coins[j]:
                        break
                    f[i] = min(f[i], f[i-coins[j]] + 1)
            return f[amount] if f[amount] != INT_MAX else -1
    

    When I use coins[j], why is it TLE? It's so interesting!


Log in to reply
 

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