LeetCode Solutions

634. Find the Derangement of An Array

Time: $O(n)$

Space: $O(n)$

			

class Solution {
 public:
  int findDerangement(int n) {
    dp.resize(n + 1);
    return find(n);
  }

 private:
  constexpr static int kMod = 1'000'000'007;
  vector<int> 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;
  }
};
			

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;
  }
}
			

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)