OJ should allow Python program to run a bit longer than the regular time limit


  • 0
    S

    DP version got TLE in couple of problems including Perfect Squares, Coin Change etc.

    Normally Python runs a bit slower than C/C++ and should have relatively loose time limit threshold.


  • 0

    @hamster Could you please paste your code here which you think should be Accepted? I can extend the time limit so your code could be Accepted. Thanks.


  • 0
    S

    @1337c0d3r Thank you.

    1. Perfect Squares
    import math
    class Solution(object):
        _dp = [0]
    
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
    
            # dp[i] is the least # of perfect square numbers which sum to i
            dp = self._dp
            for i in range(1, n + 1):
                dp.append(float('inf'))
    
            for i in range(n + 1):
                for sqn in range(1, int(math.sqrt(i)) + 1):
                    dp[i] = min(dp[i], dp[i - sqn ** 2] + 1)
    
            return dp[n]
    
    1. Coin Change (I got AC and TLE in a non consistent way.)
    class Solution(object):
        def coinChange(self, coins, amount):
            """
            :type coins: List[int]
            :type amount: int
            :rtype: int
            """
    
            dp = [float('inf') for i in range(amount + 1)]
            dp[0] = 0
    
            for coin in coins:
                for i in range(coin, amount + 1):
                    dp[i] = min(dp[i], dp[i - coin] + 1)
    
            return -1 if dp[amount] == float('inf') else dp[amount]

Log in to reply
 

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