# 634. Find the Derangement of An Array

## Approach 1: Top-down

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int findDerangement(int n) { dp.resize(n + 1); return find(n); } private: static constexpr int kMod = 1'000'000'007; vector dp; int find(int i) { if (i == 0) return 1; if (i == 1) return 0; if (dp[i]) return dp[i]; return dp[i] = (i - 1L) * (find(i - 1) + find(i - 2)) % kMod; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int findDerangement(int n) { dp = new Long[n + 1]; return (int) find(n); } private static final int kMod = 1_000_000_007; private Long[] dp; private long find(int i) { if (i == 0) return 1; if (i == 1) return 0; if (dp[i] != null) return dp[i]; return dp[i] = (i - 1) * (find(i - 1) + find(i - 2)) % kMod; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def findDerangement(self, n: int) -> int: kMod = 1_000_000_007 @functools.lru_cache(None) def dp(i: int) -> int: if i == 0: return 1 if i == 1: return 0 return (i - 1) * (dp(i - 1) + dp(i - 2)) % kMod return dp(n) 

## Approach 2: Bottom-up

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int findDerangement(int n) { constexpr int kMod = 1'000'000'007; vector dp(n + 1); dp[0] = 1; for (int i = 2; i <= n; ++i) dp[i] = (i - 1L) * (dp[i - 1] + dp[i - 2]) % kMod; return dp[n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int findDerangement(int n) { final int kMod = 1_000_000_007; int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 2; i <= n; ++i) dp[i] = (int) ((i - 1L) * (dp[i - 1] + dp[i - 2]) % kMod); return dp[n]; } } 
 1 2 3 4 5 6 7 8 9 class Solution: def findDerangement(self, n: int) -> int: kMod = 1_000_000_007 dp = [1] + [0] * n for i in range(2, n + 1): dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % kMod return dp[n]