# 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 22 23 class Solution { public: int findDerangement(int n) { vector mem(n + 1); return findDerangement(n, mem); } private: static constexpr int kMod = 1'000'000'007; int findDerangement(int i, vector& mem) { if (i == 0) return 1; if (i == 1) return 0; if (mem[i] > 0) return mem[i]; return mem[i] = (i - 1L) * (findDerangement(i - 1, mem) + // findDerangement(i - 2, mem)) % kMod; } }; 
  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) { int[] mem = new int[n + 1]; return findDerangement(n, mem); } private static final int kMod = 1_000_000_007; private int findDerangement(int i, int[] mem) { if (i == 0) return 1; if (i == 1) return 0; if (mem[i] > 0) return mem[i]; return mem[i] = (int) ((i - 1L) * (findDerangement(i - 1, mem) + // findDerangement(i - 2, mem)) % 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]