Why am I TLE


  • 0
    Q

    class Solution(object):
    def findDerangement(self, n):
    """
    :type n: int
    :rtype: int
    """
    a = [0 for _ in range(1000050)]
    a[1], a[2], a[3] = 0, 1, 2
    for i in range(4, n+1):
    a[i] = ((i-1)*(a[i-2]+a[i-1]))
    return a[n]%(1000000007)


  • 0
    Q

    class Solution(object):
    def findDerangement(self, n):

        a = [0 for _ in range(1000050)]
        a[1], a[2], a[3] = 0, 1, 2
        for i in range(4, n+1):
            a[i] = ((i-1)*(a[i-2]+a[i-1]))%(1000000007)
        return a[n]

  • 0
    N

    Using variables a and b to replace list would save you a lot of time,I guess.


  • 0

    @qsj and @nevs this solution is taking too much time creating the dp storage list of size n+1. The largest value of n is 10^6, so try changing this one line of code as follows:

    Old code: a = [0 for _ in range(1000050)]
    New code: a = [0] * 1000001

    With that one line code change, this solution is ACCEPTED in Runtime: 906 ms.

    class Solution(object):
        def findDerangement(self, n):
            a = [0] * 1000001
            a[1], a[2], a[3] = 0, 1, 2
            for i in range(4, n+1):
                a[i] = ((i-1)*(a[i-2]+a[i-1]))%(1000000007)
            return a[n]
    

Log in to reply
 

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