Leetcode 634. Find the Derangement of An Array
Problem Explanation
In this problem, a derangement is defined as a permutation of the elements of a set, such that no element appears in its original position.
Here we are given a sorted array with n integers from 1 to n. We are required to find out the total number of derangements that can be formed from this array. In other words, we need to find out the total number of ways we can rearrange the array elements such that no element ends up in its original position. The output may be extremely large so we are to return the output mod 10โน + 7.
For example, the input is 3, corresponding to the original array [1,2,3], we can count 2 derangements [2,3,1] and [3,1,2].
Solution walk-through
The solution makes use of dynamic programming to find the number of derangements for a given array. This approach is based on the fact that the number of derangements for n
is equal to (n - 1) * (derangements(n - 1) + derangements(n - 2))
.
In the solution, we define a dp
vector to cache the number of derangements for each n
. Then we apply the formula mentioned above recursively, and the recursive process stops when n
equals 0
or 1
, in which case the number of derangements is 1
or 0
, respectively.
This solution's time complexity is O(n)
, and the space complexity is also O(n)
.
Python Solution
1 2python 3class Solution: 4 kMod = 10**9 + 7 5 dp = [1, 0] 6 def findDerangement(self, n: int) -> int: 7 while len(self.dp) <= n: 8 self.dp.append((len(self.dp) - 1) * (self.dp[-1] + self.dp[-2]) % self.kMod) 9 return self.dp[n]
Java Solution:
1
2java
3public class Solution {
4 private int find(int i, int[] dp) {
5 if (i == 0) return 1;
6 if (i == 1) return 0;
7 if (dp[i] != 0) return dp[i];
8 return dp[i] = (int)(((i - 1L) * (find(i - 1, dp) + find(i - 2, dp)) % (10**9 + 7)));
9 }
10
11 public int findDerangement(int n) {
12 int[] dp = new int[n + 1];
13 return find(n, dp);
14 }
15}
JavaScript Solution
1 2javascript 3class Solution { 4 findDerangement(n) { 5 let dp = new Array(n + 1).fill(0); 6 dp[0] = 1; 7 dp[1] = 0; 8 for(let i = 2; i <= n; ++i) { 9 dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % (10**9 + 7); 10 } 11 return dp[n]; 12 } 13}
C++ Solution
1
2cpp
3class Solution {
4public:
5 static constexpr int kMod = 1000000007;
6 vector<int> dp;
7
8 int find(int i) {
9 if (i == 0)
10 return 1;
11 if (i == 1)
12 return 0;
13 if (dp[i])
14 return dp[i];
15 return dp[i] = (i - 1L) * (find(i - 1) + find(i - 2)) % kMod;
16 }
17
18 int findDerangement(int n) {
19 dp.resize(n + 1);
20 return find(n);
21 }
22};
C# Solution
1 2csharp 3public class Solution { 4 public int FindDerangement(int n) { 5 if (n == 1) { return 0; } 6 if (n == 2) { return 1; } 7 int MOD = 1000000007; 8 long[] dp = new long[n + 1]; 9 dp[1] = 0; 10 dp[2] = 1; 11 for (int i = 3; i <= n; i++) { 12 dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % MOD; 13 } 14 return (int)dp[n]; 15 } 16}
Swift Solution:
1 2swift 3class Solution { 4 func findDerangement(_ n: Int) -> Int { 5 if n == 0 { return 1 } 6 if n == 1 { return 0 } 7 8 var dp = Array(repeating: 0, count: n + 1) 9 dp[0] = 1 10 dp[1] = 0 11 12 for i in 2 ..< n + 1 { 13 dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % 1_000_000_007 14 } 15 16 return dp[n] 17 } 18}
Ruby Solution:
1 2ruby 3class Solution 4 MOD = 10**9 + 7 5 def find_derangement(n) 6 dp = [1, 0] 7 2.upto(n) do |i| 8 dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2])) % MOD 9 end 10 dp[n] 11 end 12end
Explanation
These solutions start by checking for the base cases (n=0,n=1). For n>1, they implement the recursive derangement formula (n - 1) * (derangement(n - 1) + derangement(n - 2))
, using dynamic programming to store (dp[i]) and reuse previous computed values. Afterwards, the number of total derangements for the input (n) is returned. They all run in O(n) time and use O(n) space.
These solutions can help in problems that involve combinatorial mathematics, permutations, and rearrangements, making them vital to certain areas such as cryptography, coding theory, and graph theory. At the same time, they demonstrate the use of dynamic programming to avoid redundant computations, thus optimizing the solution.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.