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] = ((i1)*(a[i2]+a[i1]))
return a[n]%(1000000007)
Why am I TLE

@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] = ((i1)*(a[i2]+a[i1]))%(1000000007) return a[n]