LeetCode 0634. Find the Derangement of An Array Solution in Java, C++, Python & Go | Explanation + Code

Description

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

You are given an integer n. There is originally an array consisting of n integers from 1 to n in ascending order, return the number of derangements it can generate. Since the answer may be huge, return it modulo 109 + 7.

 

Example 1:

Input: n = 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Example 2:

Input: n = 2
Output: 1

 

Constraints:

• 1 <= n <= 106

Solutions

Solution 1: Dynamic Programming

We define f[i] as the number of derangement of an array of length i. Initially, f[0] = 1, f[1] = 0. The answer is f[n].

For an array of length i, we consider where to place the number 1. Suppose it is placed in the j-th position, where there are i-1 choices. Then, the number j has two choices:

• Placed in the first position, then the remaining i - 2 positions have f[i - 2] derangements, so there are a total of (i - 1) × f[i - 2] derangements;
• Not placed in the first position, which is equivalent to the derangement of an array of length i - 1, so there are a total of (i - 1) × f[i - 1] derangements.

In summary, we have the following state transition equation:

$$ f[i] = (i - 1) \times (f[i - 1] + f[i - 2]) $$

The final answer is f[n]. Note the modulo operation in the answer.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

PythonJavaC++Go

class Solution: def findDerangement(self, n: int) -> int: mod = 10**9 + 7 f = [1] + [0] * n for i in range(2, n + 1): f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % mod return f[n](code-box)

class Solution { public int findDerangement(int n) { long[] f = new long[n + 1]; f[0] = 1; final int mod = (int) 1e9 + 7; for (int i = 2; i <= n; ++i) { f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % mod; } return (int) f[n]; } }(code-box)

class Solution { public: int findDerangement(int n) { long long f[n + 1]; memset(f, 0, sizeof(f)); f[0] = 1; const int mod = 1e9 + 7; for (int i = 2; i <= n; i++) { f[i] = (i - 1LL) * (f[i - 1] + f[i - 2]) % mod; } return f[n]; } };(code-box)

func findDerangement(n int) int { f := make([]int, n+1) f[0] = 1 const mod = 1e9 + 7 for i := 2; i <= n; i++ { f[i] = (i - 1) * (f[i-1] + f[i-2]) % mod } return f[n] }(code-box)

Solution 2: Dynamic Programming (Space Optimization)

We notice that the state transition equation only relates to f[i - 1] and f[i - 2]. Therefore, we can use two variables a and b to represent f[i - 1] and f[i - 2] respectively, thereby reducing the space complexity to O(1).

PythonJavaC++Go

class Solution: def findDerangement(self, n: int) -> int: mod = 10**9 + 7 a, b = 1, 0 for i in range(2, n + 1): a, b = b, ((i - 1) * (a + b)) % mod return b(code-box)

class Solution { public int findDerangement(int n) { final int mod = (int) 1e9 + 7; long a = 1, b = 0; for (int i = 2; i <= n; ++i) { long c = (i - 1) * (a + b) % mod; a = b; b = c; } return (int) b; } }(code-box)

class Solution { public: int findDerangement(int n) { long long a = 1, b = 0; const int mod = 1e9 + 7; for (int i = 2; i <= n; ++i) { long long c = (i - 1) * (a + b) % mod; a = b; b = c; } return b; } };(code-box)

func findDerangement(n int) int { a, b := 1, 0 const mod = 1e9 + 7 for i := 2; i <= n; i++ { a, b = b, (i-1)*(a+b)%mod } return b }(code-box)